리트코드 - 30. Substring with Concatenation of All Words

리트코드 - 30. Substring with Concatenation of All Words

출처 - https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

문자열 s와 문자열 배열 words가 주어집니다. 배열 words의 모든 문자열은 같은 길이를 가집니다.

연결된 문자열(Concatenated String) 이란, words의 모든 문자열을 어떤 순서로든(순열) 연속된 형태로 포함하는 문자열을 의미합니다.

• 예를 들어, words = ["ab", "cd", "ef"]일 때, "abcdef" "abefcd" "cdabef" "cdefab" "efabcd" "efcdab"은 연결된 문자열이 될 수 있습니다. 반면 "acdbef"는 words의 문자열들을 조합한 순열이 아니므로 연결된 문자열이 아닙니다.

문자열 s에서 words의 모든 문자열을 포함하는 연속된 부분 문자열을 찾으세요. 반환 순서는 상관없습니다.

풀이코드

class Solution { 
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        // 전체 문자를 한 번씩 사용한 길이
        int wl = words[0].length();
        int wn = words.length;
        int tl = wl * wn;

        // word 빈도 저장
        Map<String, Integer> wc = new HashMap<>();
        for (String word : words) {
            wc.put(word, wc.getOrDefault(word, 0) + 1);
        }

        // 탐색
        for (int i = 0; i < wl; i++) {
            int left = i;
            int right = i;
            Map<String, Integer> curCount = new HashMap<>();

            while (right + wl <= s.length()) {
                String word = s.substring(right, right + wl);
                right += wl;

                if (wc.containsKey(word)) {
                    curCount.put(word, curCount.getOrDefault(word, 0) + 1);

                    // 단어 갯수 초과시 left 이동
                    while (curCount.get(word) > wc.get(word)) {
                        String lWord = s.substring(left, left + wl);
                        curCount.put(lWord, curCount.get(lWord) - 1);
                        left += wl;
                    }

                    if (right - left == tl) {
                        result.add(left);
                    }
                } else {
                    curCount.clear();
                    left = right;
                }

            }
        }
        return result;
    }
}

생각

문제 해석이 다소 생소했는데, 예제 문장을 읽어보니 요구사항은 아래와 같이 정리할 수 있었다.

• 모든 단어를 한 번만 사용할 것
• 모든 단어를 다 사용할 것
• 모든 단어를 다 사용했을 때 s에서 시작하는 인덱스를 모두 반환

난이도가 Hard이지만 그래도 다행인 것은 "모든 단어의 길이가 같다"라는 전제조건이 있다는 것이다.

만약 단어 길이가 다르다면 재귀나 백트래킹을 사용하여 모든 인덱스를 확인해봐야 하지만, 단어의 길이가 같으니 슬라이딩 윈도우를 사용할 수 있다.

 

코드설명

정답을 만족하는 단어의 길이는 words의 단어를 모두 써야 하므로 wl = [word의 갯수 * word의 길이]가 된다.

 

1. 주어진 words에서 단어를 몇 개 썼는지 확인하기 위해 Map 구조를 사용한다. 정답 Map이 있어야 하고, 이를 확인하기 위한 현재값 확인 Map이 또 있어야 한다. 코드에서는 wc, curCount로 만들었다.

 

2. 슬라이딩 윈도우를 사용하여 탐색한다. right를 이용해서 단어 길이만큼 이동하여 잘라내는데, wc에 있는 단어라면 

curCount에 추가하여 값을 확인한다. 

 

3. 값이 있다면 wc에 있다면 curCount의 값을 추가한다.

 

3-1. wc와 비교하여 값보다 커진다면 이미 정답을 벗어난 값이므로, left를 이동해야 한다. 단어를 잘라내고, curCount에서 지우고, left도 이동해준다.

 

cf. while을 사용한 이유는 s=barfoofoo, word=[bar, foo]같은 경우 때문이다. barfoo를 추가하고 다음 시점에서 barfoofoo를 확인할텐데 이때 wc, curCount 불일치고 left 가 이동할 것이다. 그럼 foofoo가 될 텐데 이 경우에도 curCount가 초과되었을 것이므로 다시 이동하여 foo를 만들어줘야 한다.

 

3-2. curCount가 wc를 초과하지 않는지만 확인하다 right-left가 단어길이가 같아지면, 이때 left 값을 result에 추가해준다.

 

4. right을 옮겨 잘라낸 단어가 wc에 없다면 다시 처음부터 비교해야 하므로 curCount를 지우고, left를 right 위치로 이동해준다.