求问一道亚马逊的高频题

很像lc472
input如果是["cat","cats","catsdogcats"

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

一个单词是不是能被其他拼，然后在用word break2的方法拼出来。。有没有同学有简单的解法，谢谢分享

lc讨论区高赞答案我觉得改一下就可以满足需求，如果你是用dp来判断每个单词是否可拼，那么，你可以额外开辟一个int prev[] 来记录当前可拼的最后一个单次和前一次可拼的分割，最后从prev的最后一个元素开始向前查找即可。

1. def canForm(word, word_dict):
   
2.     dp = [False]*(len(word+1))
   
3.     dp[0] = True
   
4.     prev = [0]*(len(word+1))
   
5.     for i in range(1,len(word)+1):
   
6.         for j in range(i):
   
7.             if not dp[j]:
   
8.                 continue
   
9.         if word[j:i] in word_dict:
   
10.             dp[i]=True
    
11.             prev[i] = j
    
12.     if not dp[len(word)]:
    
13.         return []
    
14.     else:
    
15.         cur = len(word)
    
16.         ans = []
    
17.         while cur!=0:
    
18.             ans.insert(0,word[prev[cur],cur)
    
19.             cur = prev[cur]
    
20.         return ans

复制代码

如果你用Trie做的话，你从root到叶子节点过程中，check那个ifEnd的变量就行了，如果是True就添加一个单词

这题是LC126吧···还在努力研究中，貌似是用backtracking可以做

我用的是dfs的方法，也是discuss里别人写的

您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

可以先对原数组按每个string长度sort，因为每个词分割只能从比它短的词分割。然后直接对每个词用word break II做，worddict就是它前面的全部词

求助

可以用Trie和dfs来做，把dfs的返回值改成List<String>就好了。

1.     private int dfs(String s,int idx){
   
2.         Trie temp = root;
   
3.         if(s == null || idx >= s.length()){
   
4.             return 0;
   
5.         }
   
6.         for(int i = idx; i < s.length(); i++){
   
7.             char c = s.charAt(i);
   
8.             if(temp.next[c-'a'] == null){
   
9.                
   
10.                 return 0;
    
11.             }
    
12.             temp = temp.next[c-'a'];
    
13.             if(temp.isString && i == s.length()-1){
    
14.                 return 1;
    
15.             }
    
16.             if(temp.isString){
    
17.                 int count = dfs(s,i+1);
    
18.                
    
19.                 if(count > 0){
    
20.                     return count+1;
    
21.                 }
    
22.             }
    
23.         }
    
24.         
    
25.         return 0;
    
26.     }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yingnanzhou 发表于 2019-12-1 04:24
我也是这么想的，但是我就是不太会改成这个list,因为1个单词要输出他所有的排列组合。。

不是直接改就好了嘛？你说的排列组合是啥意思？

1.     private List<String> dfs(String s,int idx){
   
2.         Trie temp = root;
   
3.         List<String> list = new ArrayList<>();
   
4.         if(s == null || idx >= s.length()){
   
5.             return list;
   
6.         }
   
7.         for(int i = idx; i < s.length(); i++){
   
8.             char c = s.charAt(i);
   
9.             if(temp.next[c-'a'] == null){
   
10.                
    
11.                 return list;
    
12.             }
    
13.             temp = temp.next[c-'a'];
    
14.             if(temp.isString && i == s.length()-1){
    
15.                 list.add(s.substring(idx));
    
16.                 return list;
    
17.             }
    
18.             if(temp.isString){
    
19.                 List<String> res = dfs(s,i+1);
    
20.                
    
21.                 if(res.size() > 0){
    
22.                     res.add(0,s.substring(idx,i+1));
    
23.                     return res;
    
24.                 }
    
25.             }
    
26.         }
    
27.         
    
28.         return list;
    
29.     }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies