<Hard> Word Break II (LeetCode : C#)

https://leetcode.com/problems/word-break-ii/

📕 문제 설명

문자열과 단어로 구성된 딕셔너리가 주어질 때 딕셔너리 단어 중복으로 사용해서 주어진 문자열 만들 수 있는 케이스들 담아서 반환 (단어 구분은 space로)

• Input
  문자열 s (string), 단어 딕셔너리 (list)
• Output
  단어 딕셔너리 사용해 만들 수 있는 s 조합들

예제

풀이

1) 우선 wordDict의 단어들의 길이를 저장한다. (이 값을 기반으로 substring할 길이를 결정한다.)
2) 현재까지 자른 index 기준으로 1)에서 구한 길이들 만큼 substring을 한다. 만약 자른 길이가 wordDict에 존재하면 재귀를 돌려서 해당 과정을 s 길이의 sentence를 만들 때 까지 반복한다.

public class Solution {
    public IList<string> WordBreak(string s, IList<string> wordDict) {
        HashSet<int> possibleLengthSet = new HashSet<int>();
        List<string> answerList = new List<string>();
        // wordDict 내의 단어 길이들 저장 (이 길이 기준으로 s 자를거임)
        foreach(string word in wordDict)
        {
            possibleLengthSet.Add(word.Length);
        }
        // 처음 index부터 가능한 길이만큼 잘라서 wordDict에 있는지 확인 후 sentence 만드는 재귀 돌리기
        foreach(int length in possibleLengthSet)
        {
            if (length > s.Length) continue; // 만약 자를려는 길이 자체가 s보다 길면 넘기기
            string currentWord = s.Substring(0, length);
            if (wordDict.Contains(currentWord)) 
            {
                MakeWordSentence(currentWord, length);
            }
        }

        return answerList;
    
        void MakeWordSentence(string sentence, int nextIndex)
        {
            if (nextIndex >= s.Length && sentence == s) // 단어 하나만 있는 경우 answer 추가위함
            {
                answerList.Add(sentence);
                return;
            }
            // 가능한 길이들 돌면서 남은 문장에서 또 잘라서 가능하면 sentnece 에 붙여서 재귀 돌리기 
            foreach(int length in possibleLengthSet)
            {
                if (nextIndex + length > s.Length) continue;
                string currentWord = s.Substring(nextIndex, length);
                if (wordDict.Contains(currentWord)) 
                {
                    if (nextIndex + length == s.Length)
                    {
                        answerList.Add(sentence + " " + currentWord);
                    }
                    else
                    {
                        MakeWordSentence(sentence + " " + currentWord, nextIndex + length);
                    }
                    
                }
            }
        }    
    }
}

결과