알고리즘 풀이 - 문자가 포함된 문자열 찾기

문제

Word Subsets - LeetCode

 

풀이과정

- words1의 각 문자열에서 words2의 각 문자열들을  모두 포함하고 있는 문자열을 찾는 문제

- words2에서 동일한 문자가 연속으로 나온 경우 ('oo', 'pp' 등..) 연속된 형태의 문자열을 포함해야 한다.

- 문제에서 조건으로 주어진 문자열은 모두 '소문자' 라 한다.

 

결과

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList<>();
        int[] subsetEle = new int[26];

        for(String ele : words2){
            count(ele, subsetEle);
        }

        for(String word : words1){
            int[] wordEle = count(word);
            int i;
            for(i = 0; i < 26; i++){
                if(subsetEle[i] == 0) continue;
                else if(subsetEle[i] > wordEle[i]) break;
            }
            if(i == 26) result.add(word);
        }
        return result;
    }

    public int[] count(String  word){
        int[] result = new int[26];
        for(char ele : word.toCharArray()){
            result[ele - 'a'] += 1;
        }
        return result;
    }

    public void count(String  word, int[] container){
        int[] result = new int[26];
        for(char ele : word.toCharArray()){
            result[ele - 'a'] += 1;
        }
        for(int i = 0; i < 26; i++){
            if(container[i] < result[i]) container[i] = result[i];
        }
    }
}

 

- 소문자만 사용한다는 조건이 있었으므로 map 대신 int 배열을 활용하면 속도가 빨라질 수 있다.

- 26길이의 int 배열(subsetEle)을 선언하고 문자열 수를 비교한다.

ex) a => subsetEle['a' - 'a'] += 1, oo => subsetEle['o' - 'a'] += 2 ..

- words1의 각 문자열마다 int배열 wordEle를 받는다.

- 배열 subsetEle 와 같은 배열 wordEle가 나오면  result 리스트에 문자열을 포함시킨다.