[LeetCode] 140. Word Break II

140. Word Break II

Hard

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

 

Example 1:

Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]

Example 2:

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []

 

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

---

문제 풀이

• 주어진 단어 리스트에 속해있는 단어들로 입력받은 문장을 만들 수 있는지 확인한다. 
• 만약 문장에 단어들이 모두 들어가있다면, 단어 리스트들을 순서대로 띄어쓰기를 추가하여 문장을 답으로 추가한다. 
• 제한사항을 보면 문장의 최대길이는 20이며, 단어 리스트들의 개수 최대는 1000개이다. N^2의 알고리즘에도 문제가 풀릴 수 있다. 
• BFS를 이용하여 문제를 풀 수 있다. 
• 주어진 단어 리스트들을 호출할때 시간복잡도를 줄이기 위해 딕셔너리로 치환한다. 
• 그리고 BFS에서 각각 사용할 인덱스 시작값과 각 단어들로 구성될 정답 리스트를 클래스로 구성한다. 
• 시작 인덱스부터 주어진 문장의 끝 인덱스 + 1 까지 모든 길이의 단어들을 각각 확인해야한다.
• 이 단어들이 해당 딕셔너리에 존재하는지 확인하고, 끝 인덱스를 다음 노드에 넣고 딕셔너리에서 찾은 단어를 노드 답 리스트에 넣는다.
• 매번 확인된 단어들의 끝 인덱스 위치, 문장안의 인덱스에서부터 문장의 종료 지점까지 계속해서 단어들을 찾으며 BFS를 진행한다.
• 만약 객체의 인덱스가 문장의 끝이라면, 모든 단어들이 선택되고 정답이 객체에 들어 있기 때문에, 문제 정답 리스트에 문장을 만들어 넣어준다.

 

소스 코드

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        hash_set = set(wordDict)
        ans = []
        q = []
        class Node:
            def __init__(self, idx):
                self.index = idx
                self.ans = []
        start = Node(0)
        q.append(start)
        while q:
            cur = q.pop(0)
            if cur.index == len(s):
                ans.append(' '.join(cur.ans))
            for i in range(cur.index + 1, len(s) + 1):
                nxt_s = s[cur.index:i]
                if nxt_s in hash_set:
                    nxt = copy.deepcopy(cur)
                    nxt.index = i
                    nxt.ans.append(nxt_s)
                    q.append(nxt)
        return ans