[LeetCode] 140. Word Break II

 轉自LeetCode

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.

Solution

139 Word Break 的衍生題

難度直接變成 hard

看到這個求排列組合，很高機率會是用 DFS 來解

因為題目沒有要求順序，代表任何一個在 wordDict 裡面的 word 都可以拿來用

且可以重複使用

因此，每一次都從 wordDict 裡面拿 word 出來，看看當下字串的開頭是否剛好等於其中一個

是的話，將剩下的部分，用 DFS 重複檢查

結束條件就是 s 為空字串的時候，這代表已經將 s 都切割好了

然後組合的時候，如果回傳的字串是空字串，前面不用加空白，因為代表是字串結束

Kotlin

	class Solution {
	fun wordBreak(s: String, wordDict: List<String>): List<String> {
	return dfs(s, wordDict)
	}
	fun dfs(s: String, wordDict: List<String>): List<String> {
	return if (s.isEmpty()) {
	listOf("")
	} else {
	val result = mutableListOf<String>()
	for(w in wordDict) {
	if (s.length < w.length || s.substring(0,w.length) != w) {
	continue
	}
	val remaining = dfs(s.substring(w.length), wordDict)
	for(str in remaining) {
	if(str.isEmpty()) {
	result.add(w)
	} else {
	result.add(w + " " + str)
	}
	}
	}
	result
	}
	}
	}

view raw word_break_II.kt hosted with ❤ by GitHub