[Java] leetcode 30. Substring with Concatenation of All Words

문제

https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/

Substring with Concatenation of All Words - LeetCode

풀이

풀이 알고리즘은 다음과 같다.

1. 주어진 words 로 각 문자열 출현 개수를 카운트 한다.
2. 주어진 문자열 s 의 인덱스를 선형 탐색하면서 다음을 수행한다.
   1. words 배열의 문자 하나 길이 = len 이라 하면, s의 substring을 만든다.
   2. s.substring 을 카운트해서 알고리즘 1 에서 만든 카운트 보다 크면 break을 건다.
   3. words 의 길이만큼 탐색 한 경우, ans에 현재 인덱스 i를 추가한다.

 

처음에words Count 를 만드는 방법이 아닌, 주어진 문자열 S를 선형 탐색하여 HashMap<String, List<Integer>> 맵을 만든다음  words배열 인덱스를 백트레킹으로 브루트 탐색하였는데 위의 알고리즘처럼 조기 종료가 없어서 TLE가 떴다. 

 

초기 맵 구성을 s 에서 만드는 것이 아닌 words 배열을 이용하여 문제를 풀었더니 풀렸다.

 

코드

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        HashMap<String, Integer> wordCnt =  new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int n = words.length;
        int len = words[0].length();
        String str;

        for(String x : words)wordCnt.put(x, wordCnt.getOrDefault(x,0)+1);

        for(int i =0 ;i < s.length() - (n*len)+1 ;i ++){
            HashMap<String, Integer> lookAtI = new HashMap<>();//i번째를 봅니다.
            int j = 0;
            while(j < n){
                str = s.substring(i + j*len , i+(j+1)*len);
                if(!wordCnt.containsKey(str))break;
                lookAtI.put(str, lookAtI.getOrDefault(str,0)+1);
                if(wordCnt.get(str) < lookAtI.get(str))break;
                j++;
            }
            if(j == n){
                ans.add(i);
            }
        }
        return ans;
    }
}