黑车电面(超新鲜!!!!)

splendidLQX 发表于 2018-11-28 05:15
图的搜索就是O（V + E）   然后算算图中有多少条边就好了

但是不是图当中可以重复利用么，就是走一个环可以不断的走

飞天sb飞翔 发表于 2018-11-29 07:24
但是不是图当中可以重复利用么，就是走一个环可以不断的走

不会的   新句子的长度跟原句子的长度是一样的   所以stack的深度最大是length
关键点就是边的大小了   

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

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

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

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

splendidLQX 发表于 2018-11-29 09:25
这题不是特别好想   但是O(n ^ n)是不可能的
因为图的建立只跟前后单词有关系    而且要是碰到重复的边 ...

多谢了哈

飞天sb飞翔 发表于 2018-11-29 11:40
多谢了哈

小事   字数字数字数字数

splendidLQX 发表于 2018-11-29 11:41
小事   字数字数字数字数

字数什么意思啊 我是地里的小白

飞天sb飞翔 发表于 2018-11-30 02:24
字数什么意思啊 我是地里的小白

回复有字数限制哈    字数不够没法回复   哈哈

splendidLQX 发表于 2018-11-30 04:45
回复有字数限制哈    字数不够没法回复   哈哈

hahah 紫薯紫薯

1. import java.util.*;
   
2. import java.io.*;
   
3. 
   
4. class Solution {
   
5.     public List<List<String>> reconstructWordList(List<String> words) {
   
6.         List<List<String>> results = new ArrayList<>();
   
7.         if(words == null || words.size() == 0) {
   
8.             return results;
   
9.         }
   
10. 
    
11.         // word => successor
    
12.         Map<String, Set<String>> map = new HashMap<>();
    
13.         for(int i = 0; i < words.size() - 1; i++) {
    
14.             Set<String> set;
    
15.             if(!map.containsKey(words.get(i))) {
    
16.                 set = new HashSet<>();
    
17.             } else {
    
18.                 set = map.get(words.get(i));
    
19.             }
    
20.             set.add(words.get(i + 1));
    
21.             map.put(words.get(i), set);
    
22.         }
    
23. 
    
24.         for(String word : map.keySet()) {
    
25.             List<String> tmp = new ArrayList<>();
    
26.             tmp.add(word);
    
27.             helper(word, map, words.size(), tmp, results);
    
28.         }
    
29. 
    
30.         return results;
    
31.     }
    
32. 
    
33.     public void helper(String word, Map<String, Set<String>> map, int len, List<String> cur, List<List<String>> results) {
    
34.         if(cur.size() == len) {
    
35.             results.add(new ArrayList<>(cur));
    
36.             return;
    
37.         }
    
38.         
    
39.         if(map.containsKey(word)) {
    
40.             for (String successor : map.get(word)) {
    
41.                 cur.add(successor);
    
42.                 helper(successor, map, len, cur, results);
    
43.                 cur.remove(cur.size() - 1);
    
44.             }
    
45.         }
    
46.     }
    
47. 
    
48.     public static void main(String[] args) {
    
49.         List<String> input = Arrays.asList("A", "B", "C", "A", "E");
    
50. 
    
51.         String str = "he is good and he and great";
    
52.         List<String> input2 = Arrays.asList(str.split(" "));
    
53. 
    
54.         Solution s = new Solution();
    
55.         for(List<String> result : s.reconstructWordList(input2)) {
    
56.             for(String word : result) {
    
57.                 System.out.print(word + ", ");
    
58.             }
    
59.             System.out.println();
    
60.         }
    
61.     }
    
62. }

复制代码

Java版本，类似蠡口思丝斯，有些小细节还是要注意，多谢楼主