发个口袋宝石OA+电1电2面经

lj910817 发表于 2017-7-12 07:07
要先排序把，每次往前扫，str和string是一组，ing和string是一组

对的要排序，我之前想了一个图的方法，每个String 看做一个Vertex， 建立一个邻接矩阵记录两两间是否为子串， 单向图，





最后数单向最长的路径数， 如上图依次是 1，2，2，1， 大家帮我看看这个思路有没有问题

其实就是按长度排好序，然后建一个Map<String, Set<String>>, 这里Set<String>是所有该string能组合成的parent string， 好拗口，这么写parentString.indexOf(string) != -1大家就懂了.
然后每次除了更新自己的parent string，还要回过头去更新所以以自己为parent string的 string，把祖先string从它那里移除, 举例， ring可以到tring和string， 发现tring能到string，然后回过头把ring里的string去掉
最后用一个visited set来过一遍所有string，看有多少条path（有向）

感觉这个电面二有点难啊。。。

我目前的思路是首先按String长度从大到小排序然后遍历。用tree的结构来表示substring的关系，比如case4总的话root就是“string", “string”的一个children就是“tring“， 这时遍历到ring的时候就再之前已经建立好的tree去找其对应的位置，这个例子中对应的位置就是”tring“的children。  所有string遍历完成后再找建立好的所有tree的leaf的个数就是最后的结果。

找每个string的位置的时候需要遍历所有之前的string， 所以时间复杂度应该是O(n^2)。大家看下这个思路是不是对的。

补充内容 (2017-7-25 12:57):
时间复杂度好像不对，因为每次找位置的时候都得用到indexOf或者strStr（），这个复杂度我没计算在内。。。

jili 发表于 2017-7-12 07:18
对的要排序，我之前想了一个图的方法，每个String 看做一个Vertex， 建立一个邻接矩阵记录两两间是否为子 ...

尝试着写了一个 但是不能handle duplicate, 如果handle duplicate 改动应该也不大

1. public static List<String> partitionStr(String[] strs) {
   
2.             Arrays.sort(strs, (String a, String b) -> a.length() - b.length());
   
3.             Map<String, Set<String>> parentStr = new HashMap<>();
   
4.             for (int i = 0; i < strs.length; i++) {
   
5.                     for (int j = i + 1; j < strs.length; j++) {
   
6.                             if (strs[j].indexOf(strs[i]) == -1) {
   
7.                                     continue;
   
8.                             }
   
9.                             Set<String> s = parentStr.getOrDefault(strs[i], new HashSet<>());
   
10.                             s.add(strs[j]);
    
11.                             parentStr.put(strs[i], s);
    
12.                     }
    
13.             }
    
14.            
    
15.             List<String> res = new ArrayList<>();
    
16.             Set<String> visited = new HashSet<>();
    
17.             for (int i = 0; i < strs.length; i++) {
    
18.                     if (parentStr.containsKey(strs[i])) {
    
19.                             for (String val: parentStr.get(strs[i])) {
    
20.                                     if (parentStr.containsKey(val)) {
    
21.                                             parentStr.put(strs[i], nonIntersect(parentStr.get(strs[i]), parentStr.get(val)));
    
22.                                     }
    
23.                             }
    
24.                     }
    
25.             }
    
26.             for (int i = 0; i < strs.length; i++) {
    
27.                     if (!parentStr.containsKey(strs[i])) {
    
28.                             continue;
    
29.                     }
    
30.                     path(parentStr, res, "", visited, strs[i]);
    
31.             }
    
32.             return res;
    
33.     }
    
34.    
    
35.     public static void path(Map<String, Set<String>> map, List<String> res, String cur,
    
36.                     Set<String> visitedKey, String key) {
    
37.             if (visitedKey.contains(key)) {
    
38.                     return;
    
39.             }
    
40.             if (map.containsKey(key)) {
    
41.                     for (String val: map.get(key)) {
    
42.                             path(map, res, cur + key + " ", visitedKey, val);
    
43.                     }
    
44.                     visitedKey.add(key);
    
45.             } else {
    
46.                     res.add(cur + key);
    
47.                     return;
    
48.             }
    
49.     }
    
50.    
    
51.     public static Set<String> nonIntersect(Set<String> a1, Set<String> a2) {
    
52.             Set<String> res = new HashSet<>();
    
53.             for (String val: a1) {
    
54.                     if (!a2.contains(val)) {
    
55.                             res.add(val);
    
56.                     }
    
57.             }
    
58.             return res;
    
59.     }

复制代码

感觉第2题像是topological sort，先用字符串两两配对检查是不是有从属关系建立一个有向图，然后进行dfs访问所有path，一边移除所有访问过的图上的edge

没见过第二题，马上面pg 谢谢lz

好难的题。。