leetcode(140) - 单词拆分II
一、题目描述
1 英文版
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
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: []
2 中文版
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
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: []
二、ruby方案
2.1 思路
需要返回所有结果,那么回溯基本上跑不了了。
不过这道题不能强行回溯,会超时的,需要用到上一题的动态规划先判断字符串能不能被拆分,如果可以再进行回溯。
2.2 代码实现
# @param {String} s
# @param {String[]} word_dict
# @return {String[]}
def word_break(s, word_dict)
# 深搜
split_flag = can_break?(s, word_dict)
if split_flag[-1]
word_dict = word_dict.uniq
res_list, array = [], []
return word_break_dfs(s, word_dict, res_list, array, split_flag, s.size, 0)
else
[]
end
end
def word_break_dfs(s, word_dict, res_list, array, split_flag, length, start)
if start == length - 1
res_list << array
return
end
start.upto(length - 1).each do |index|
str = s[start..index]
if word_dict.include? str
array << str
word_break_dfs(s, word_dict, res_list, array, split_flag, length, index)
end
end
end
def can_break?(s, word_dict)
length = s.size
split_flag = Array.new(length + 1, false)
split_flag[0] = true
1.upto(length).each do |i|
0.upto(i - 1).each do |j|
if split_flag[j] && word_dict.include?(s[j...i])
split_flag[i] = true
break
end
end
end
split_flag
end
Show Disqus Comments