广州网站设计哪里好,金蝶软件公司简介,世界比分榜,wordpress评价功能单词拆分 II
力扣链接#xff1a;140. 单词拆分 II
题目描述
给定一个字符串 s 和一个字符串字典 wordDict #xff0c;在字符串 s 中增加空格来构建一个句子#xff0c;使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意#xff1a;词典中的…单词拆分 II
力扣链接140. 单词拆分 II
题目描述
给定一个字符串 s 和一个字符串字典 wordDict 在字符串 s 中增加空格来构建一个句子使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意词典中的同一个单词可能在分段中被重复使用多次。
示例
示例 1
输入:s “catsanddog”, wordDict [“cat”,“cats”,“and”,“sand”,“dog”] 输出:[“cats and dog”,“cat sand dog”] 示例 2
输入:s “pineapplepenapple”, wordDict [“apple”,“pen”,“applepen”,“pine”,“pineapple”] 输出:[“pine apple pen apple”,“pineapple pen apple”,“pine applepen apple”] 解释: 注意你可以重复使用字典中的单词。 示例 3
输入:s “catsandog”, wordDict [“cats”,“dog”,“sand”,“and”,“cat”] 输出:[]
Java代码
class Solution {private ListString tem new ArrayList();private ListString res new ArrayList();public ListString wordBreak(String s, ListString wordDict) {dfs(0, wordDict, s);return res;}public void dfs(int start, ListString wordDict, String s) {if(start s.length()) {StringBuilder sb new StringBuilder();for(String ar : tem) sb.append(ar );res.add(sb.toString().trim());return;}for(int i start; i s.length(); i) {if(wordDict.contains(s.substring(start, i 1))) {tem.add(s.substring(start, i 1));dfs(i 1, wordDict, s);if(!tem.isEmpty()) {tem.remove(tem.size() - 1);}}}}
}
