문제

You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.

You can return the answer in any order.

제한사항

• 1 <= s.length <= $10^4$
• s consists of lower-case English letters.
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 30
• words[i] consists of lower-case English letters.

접근 1

Hard 난이도의 문제라 다소 긴장했었습니다. 주어진 문자열에서 문자집합의 조합을 통한 문자열의 인덱스 위치들을 반환하는 문제였어요. 제한사항을 보아도 브루트-포스 방식으로 풀면 안된다는 것을 알았고 처음 생각한 방법은,

1. 문자열에서 주어진 문자들의 위치를 모두 찾는다.
2. 깊이 우선 탐색dfs를 통해 다음 위치 인덱스에 사용되지 않은 문자 집합의 요소를 찾아 이어준다.
3. 전부다 사용했다면 해당 인덱스를 답에 추가한다.

하지만 이 방식은 시간 초과가 나더라구요... "a * 10000" 문자열과 words 안에 "a"가 5000개가 들어가면 결국 모든 경우의 수를 탐색해서 브루트-포스했을 경우의 속도와 같은 경우가 되는 것 같습니다.

답안(풀이 실패)

class Solution {

    private boolean[] checks = new boolean[5000];

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();

        List<Integer>[] wordPoses = new ArrayList[words.length];
        Map<String, List<Integer>> mapForWordPoses = new HashMap<>();
        for(int i = 0; i < words.length; ++i){
            List<Integer> posInfo = mapForWordPoses.get(words[i]);
            if(posInfo == null){
                wordPoses[i] = getWordPoses(s, words[i]);
                mapForWordPoses.put(words[i], wordPoses[i]);
            } else{
                wordPoses[i] = posInfo;
            }
        }
        
        int wordCnt = words[0].length();
        List<String> doubleCheck = new ArrayList<>();
        for(int i = 0; i < wordPoses.length; ++i){
            boolean isDoubleCheck = false;
            for(int j = 0; j < doubleCheck.size(); ++j){
                if(doubleCheck.indexOf(words[i]) >= 0){
                    isDoubleCheck = true;
                    break;
                }
            }
            if(isDoubleCheck)
                continue;
            
            checks[i] = true;
            for(int j = 0; j < wordPoses[i].size(); ++j){
                int startIndex = wordPoses[i].get(j);
                if(ret.indexOf(startIndex) >= 0)
                    continue;
                
                if(dfs(s, wordCnt, wordPoses, 1, startIndex))
                    ret.add(startIndex);
            }
            checks[i] = false;
        }

        return ret;
    }

    private List<Integer> getWordPoses(String s, String word){
        List<Integer> ret = new ArrayList<>();
        int offset = 0;
        while((offset = s.indexOf(word, offset)) >= 0){
            ret.add(offset);
            offset += 1;
        }
        return ret;
    }

    private boolean dfs(String s, int wordCnt, List<Integer>[] wordPoses, int concatCnt, int curStringIndex){
        if(concatCnt >= wordPoses.length){
            return true;
        }

        for(int i = 0; i < wordPoses.length; ++i){
            if(checks[i]){
                continue;
            }

            checks[i] = true;

            boolean isValid = false;
            for(int j = 0; j < wordPoses[i].size(); ++j){
                int pos = wordPoses[i].get(j);
                if(pos == curStringIndex + wordCnt){
                    if(isValid = dfs(s, wordCnt, wordPoses, concatCnt + 1, pos))
                        break;
                }
            }

            checks[i] = false;

            if(isValid)
                return true;
        }

        return false;
    }


}

접근2

결국에 다른 분들의 답과 유튜브를 보고 참고해서 풀었습니다. 보는 순간 머리가 뻥 뚫리는 기분었네요. 방식은 저와 비슷했지만, Map을 통해 count를 비교해서 풀이했습니다.

아침에 풀이를 보고 퇴근하고 집에 와서 복기해보니 결국 방식은 같았으니 조금만 더 생각해도 풀 수 있는 문제였다고 생각했어요. 실제로 알고리즘 테스트 문제를 풀 때 주구장창 사용한게 Map이었는데 말이죠... java의 Collection 개념이 아직 미숙해서 이를 활용할 생각을 안했던 것 같습니다...반성합니다.

답안

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();

        int wordCnt = words[0].length();
        int wordsSize = words.length;
        if(s.length() < wordCnt * wordsSize)
            return ret;

        Map<String, Integer> wordMap = new HashMap<>();
        for(String word : words){
            wordMap.put(word, wordMap.getOrDefault(word, 0) + 1);
        }

        StringBuilder sb = new StringBuilder(s);
        for(int i = 0; i <= s.length() - wordCnt * wordsSize; ++i){
            Map<String, Integer> wordMap2 = new HashMap<>();
            int count = 0;
            for(int j = i; j <= s.length() - wordCnt; j += wordCnt){
                String word = sb.substring(j, j + wordCnt);
                if(!wordMap.containsKey(word))
                    break;
                
                wordMap2.put(word, wordMap2.getOrDefault(word, 0) + 1);
                if(wordMap2.get(word) <= wordMap.get(word)){
                    ++count;
                } else{
                    break;
                }
            }
            if(count == wordsSize){
                ret.add(i);
            }
        }

        return ret;
    }
}

참고

Coding Simplified 유튜브
만냥이님 Velog