LeetCode: 30번 (Substring with Concatenation of All Words) [JAVA]

문제 링크

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

Substring with Concatenation of All Words - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 words 배열을 돌며 word의 인덱스화, 중복된 word 개수 카운트
2. 이중 반복문(i=0 부터 word 길이만큼, j=i 부터 s의 길이만큼)을 진행하며 탐색
   1) 우선 현 위치(j)부터 word 길이만큼의 문자열을 가져와 해당 문자열이 기존에 있다면 해당 개수를 +1하며 표시를, 반대로 없다면 기존의 정보를 모두 초기화하고 다음 탐색 진행
   2) 만약 해당 탐색을 하며 탐색한 단어의 개수가 word 개수만큼 진행했다면, 여태까지 탐색이 concatenated substring인지 판별
   3) 이후 해당 구간 중에서 가장 앞의 문자열을 가져와 기존에 있는 문자열이라면 개수 - 1 진행
3. answer 반환

 문제에서 주어진 s와 words 배열을 바탕으로 특정 구간이 concatenated substring인지를 판별해, 해당 구간들의 인덱스를 모아 반환해야 하는 문제이다. 다만 순차적으로 s의 시작부터 끝까지 해당 구간을 자르고 구간 속 단어들을 판별하는 경우에는 필요 이상의 반복 탐색으로 시간초과로 이어질 수 있다. 이에 해결책으로 구간을 하나씩 증가하며 탐색하는 것이 아닌 word 길이만큼 증가하는 방식을 사용하여, 이전에 탐색한 구간 속 word들의 정보에서 앞부분 문자열의 정보를 제거하고 뒤에 추가되는 부분만의 문자열을 따로 추가하는 방식으로 이전 정보를 재활용하여 탐색을 쉽게 이어가는 방법을 사용했다.
 우선 전체 words 배열을 한 번 돌며 word의 인덱스화와 전체 word들의 개수를 카운트한다. 그 다음에는 이중 for문을 통해 탐색을 진행하여 앞서 설명한 방식을 적용한다. 우선 현재 위치에서 주어진 word의 길이(혹은 마지막 위치까지)만큼의 부분 문자열을 가져온다. 그 이후에 해당 부분 문자열이 기존 words 배열에 있다면 해당 개수에 +1을 진행해주고, 만약 없다면 해당 부분 이전까지의 구간 모두 concatenated substring이 될 수 없기에 모든 정보를 초기화 해버리고 다음 탐색으로 넘어간다. 이후 여태까지 탐색을 진행한 단어(부분 문자열)의 개수가 words 배열의 길이만큼이라면, 해당 구간이 concatenated substring인지 확인하고, 만약 맞다면 해당 구간의 시작 인덱스를 answer에 추가한다. 이후에는 다음 구간의 탐색을 위해 현 구간 가장 앞부분의 문자열에 관한 정보를 제거한다. 그렇게 탐색을 마치고 시작 인덱스가 누적된 answer를 반환하면 된다.

 

class Solution {
    HashMap<String, Integer> wordIndex = new HashMap<>(), wordCount = new HashMap<>();

    public List<Integer> findSubstring(String s, String[] words) {
        int wordLength = words[0].length(), searchCount;
        int[] wordContain = new int[words.length];
        List<Integer> answer = new ArrayList<>();

        for (int i = 0; i < words.length; i++) {//기존 words 배열을 돌며 
            wordIndex.put(words[i], i);//word의 인덱스화

            if (wordCount.containsKey(words[i])) {//중복된 word들의 개수 포함
                wordCount.replace(words[i], wordCount.get(words[i]) + 1);
            } else {
                wordCount.put(words[i], 1);
            }
        }

        for (int i = 0; i < wordLength; i++) {//한 개의 word 길이만큼
            searchCount = 0;
            Arrays.fill(wordContain, 0);

            for (int j = i; j < s.length();) {//s 길이만큼
                String substr;

                if (j + wordLength >= s.length()) {//현 위치부터 word 길이만큼의 문자열 가져오기
                    substr = s.substring(j);
                } else {
                    substr = s.substring(j, j + wordLength);
                }

                j += wordLength;//word 길이만큼 건너뛰기

                if (wordIndex.containsKey(substr)) {//기존에 있는 문자열에 있다면
                    ++wordContain[wordIndex.get(substr)];
                    ++searchCount;
                } else {//없다면 초기화
                    searchCount = 0;
                    Arrays.fill(wordContain, 0);
                }

                if (searchCount == words.length) {//word 개수만큼의 탐색을 완료했다면
                    int startIndex = j - wordLength * words.length;

                    if (isConcatenatedSubstring(wordContain)) {//concatenated substring이라면
                        answer.add(startIndex);
                    }

                    String removeString = s.substring(startIndex, startIndex + wordLength);//구간 앞부분의 문자열

                    if (wordIndex.containsKey(removeString)) {//앞부분 문자열 제거
                        --wordContain[wordIndex.get(removeString)];
                    }

                    --searchCount;
                }
            }
        }

        return answer;
    }

    boolean isConcatenatedSubstring(int[] wordContain) {//해당 구간이 concatenated substring인지
        for (Map.Entry<String, Integer> entry : wordCount.entrySet()) {
            if (wordContain[wordIndex.get(entry.getKey())] != entry.getValue()) {
                return false;
            }
        }

        return true;
    }
}

결과