73일 (1160. Find Words That Can Be Formed by Characters) String

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

 

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length, chars.length <= 100
• words[i] and chars consist of lowercase English letters.

 

- 접근방법 

chars가 words[i]를 모두 포함하면 true, 아니라면 false를 리턴하는 함수 matchingWords를 만들었다.

 

각각의 words[i]가 chars의 부분집합인 경우라면(matchingWords 함수가 true라면)

cnt에 words[i]의 단어길이를 더하고 cnt를 리턴하였다.

 

 

- 코드

class Solution {
    public int countCharacters(String[] words, String chars) {
        int cnt = 0;

        for(int i = 0; i < words.length; i++) {
            StringBuilder keyWord = new StringBuilder(chars);
            // words[i]가 keyWord의 부분집합이라면? 
            if(matchingWords(words[i], keyWord)) cnt += words[i].length();
        }

        return cnt;
    }

    private boolean matchingWords(String word, StringBuilder keyWord) {
        for(int j = 0; j < word.length(); j++) {
            int keyWordIdx = keyWord.indexOf(word.charAt(j)+"");

            if(keyWordIdx != -1) {
                keyWord.deleteCharAt(keyWordIdx); // 공통된 문자열은 소거한다.
            } else return false; // keyWord에 속하지않는 word의 값이 존재한다면 false
        }

        return true;
    }
}

 

그럭저럭 성능을 보여주는 방법이지만 직관적으로 이해하기 편해서 사용하였다.

 

 

 

https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/

Find Words That Can Be Formed by Characters - LeetCode