<Hard> Substring with Concatenation of All Words (LeetCode : C#)

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

📕 문제 설명

문자열 s와 같은 길이의 단어가 담긴 배열이 주어진다. 단어 배열의 단어들로 가능한 모든 순열을 가지는 s의 부분 문자열의 시작 index를 모두 담아 반환하기

없으면 빈 리스트 반환
같은 단어 존재함

• Input
  문자열 s, 같은 길이의 단어가 담긴 배열
• Output
  단어들의 순열을 가지는 s의 부분문자열의 모든 시작 index

예제

현재 단어는 foo와 bar이 주어졌다. 가능한 순열은 foobar와 barfoo이다. s에서 barfoo의 시작 index인 0, foobar의 시작 index인 9를 반환한다.

풀이

처음부터 효율성 너무 따지면서 풀다가 돌아돌아 끝냈다.. 원래 시도했던것은 이렇게 index별로 다 확인하는게 아니라 단어 확인할 때 마다 안되는 케이스면 그 직전 데이터(?)로 돌아가서 확인하는식으로 하고 있었는데 잘 안되어서 생각나는 쉬운 방법으로 변경해서 풀었다.

1. s의 모든 index 별로 확인 (어떤 부분에서 단어 만들어질지 모르기에)
2. 단어 배열의 단어 수 만큼 단어들을 모아 확인
   2-1) 단어 배열 내 없는 단어 접근 시 break
   2-2) 단어 배열 내 있지만 더 많은 개수라면 break
   2-3) 현재 for문을 돌며 저장된 단어들의 개수와 단어 배열 내 단어 수 같으면 startIndex answer에 저장

public class Solution {
    public IList<int> FindSubstring(string s, string[] words) {
        List<int> answer = new List<int>();
        Dictionary<string, int> wordCountDict = new Dictionary<string, int>();
		// word : count 정보
        foreach(string word in words)
        {
            if (wordCountDict.TryGetValue(word, out int count)) wordCountDict[word] += 1;
            else wordCountDict.Add(word, 1);
        }

        int wordLength = words[0].Length;
        int totalWordsCount = words.Length;
        Dictionary <string, int> currWordCountDict = new Dictionary<string, int>();
        // 모든 index별로 단어 확인
        for (int i = 0; i < s.Length; i ++)
        {
        	// 현재 index에서 단어 배열 내 단어 수만큼 못만들면 끝
            if (i + (wordLength * totalWordsCount) > s.Length) break;
            currWordCountDict.Clear();
            // 단어 배열 내 단어 수 만큼 반복
            for (int j = 0; j < totalWordsCount; j++)
            {
                string currS = s.Substring(i + j * wordLength, wordLength);
                // 단어 배열 내 존재하는 단어인 경우
                if (wordCountDict.TryGetValue(currS, out int maxCount))
                {
                	// 현재 저장된 단어면 단어 배열 내 단어 개수와 비교
                    if (currWordCountDict.TryGetValue(currS, out int count))
                    {
                    	// 이미 max면 break
                        if (count == maxCount) break;
                        currWordCountDict[currS] += 1;
                    }
                    else // 저장안되어 있으면 저장
                    {
                        currWordCountDict.Add(currS, 1);
                    }
                }
                else break; // 단어 배열 내 존재 x -> break
            }
            // 저장된 단어 수 == 단어 배열 내 단어 수 -> 답 추가
            if(currWordCountDict.Sum(x => x.Value) == totalWordsCount)
            {
                answer.Add(i);
            }
        }

        

        return answer;
        
    }
}

결과