[leetcode]140. Word Break II, 파이썬

문제

---

• 릿코드 문제 링크

풀이

---

• 난이도 : hard
• 풀이, dfs
• 주어진 wordDict을 돌며 해당 단어로 시작하면 재귀로 돌려줌
• s가 빈 채로 인자로 넘어왔다는 뜻은 주어진 wordDict 배열 원소로 문장 s가 완성 가능하다는 뜻이므로 ret에 words 리스트를 더해줌
• 문제 조건에 맞춰 리턴

코드

---

class Solution:
    def wordBreak(self, s, wordDict):
        ret = []
        self.dfs(s, wordDict, ret, [])
        for i, e in enumerate(ret) :
            ret[i] = ' '.join(e)
        return ret

    def dfs(self, s, wordDict, ret, words):
        if not s: 
            ret.append(words)
        for word in wordDict:
            if not s.startswith(word):
                continue
            self.dfs(s[len(word):], wordDict, ret, words + [word])