求指点，亚麻OA题

求指点
https://aonecode.com/amazon-online-assessment-find-substrings

非常非常brute force的solution，答案应该是正确的但是timeout了。
整体思路就是先找1个character 再找2个character。。。。一直到n - 1 character (当然找1character的时候碰到"bb"的话需要添加在一起）。

我的方法非常笨，希望有大神能帮忙优化。

1. public static List<String> findSubstrings(String input) {
   
2.         
   
3.         List<String> result = new ArrayList<>();
   
4.         for (int i = 0; i < input.length() - 1; i++) {
   
5.             List<String> temp = helper(input, i);
   
6.             if (temp.size() > result.size()) {
   
7.                 result = temp;
   
8.             }
   
9.         }
   
10.         if (result.size() == 0) {
    
11.             result.add(input);
    
12.         }
    
13.         
    
14.         return result;
    
15.     }
    
16.    
    
17.     private List<String> helper(String input, int num) {
    
18.         Map<String, StringBuilder> builderMap = new HashMap<>();
    
19.         Map<String, Integer> indexMap = new HashMap<>();
    
20.         Set<Character> failedSet = new HashSet<>();
    
21.         int right = 0;
    
22.         while (right < input.length()) {
    
23.             if (right + num > input.length()) {
    
24.                 addToFailedSet(failedSet, input.substring(right));
    
25.                 break;
    
26.             }
    
27.             
    
28.             String rval = input.substring(right, right + num);
    
29.             if (!isValid(failedSet, rval)) {
    
30.                 addToFailedSet(failedSet, rval);
    
31.             } else {
    
32.                 if (!indexMap.containsKey(rval)) {
    
33.                     indexMap.put(rval, right);
    
34.                     builderMap.put(rval, new StringBuilder());
    
35.                     builderMap.get(rval).append(rval);
    
36.                 } else {
    
37.                     int index = indexMap.get(rval);
    
38.                     if (index == right - num) {
    
39.                         indexMap.put(rval, right);
    
40.                         builderMap.get(rval).append(rval);
    
41.                     } else {
    
42.                         builderMap.remove(rval);
    
43.                         addToFailedSet(failedSet, rval);
    
44.                     }
    
45.                 }
    
46.             }
    
47.             right += num;
    
48.         }
    
49.         
    
50.         List<String> result = new ArrayList<>();
    
51.         for (String key: builderMap.keySet()) {
    
52.             if (isValid(failedSet, key)) {
    
53.                 result.add(builderMap.get(key).toString());
    
54.             }   
    
55.         }
    
56.         return result;
    
57.     }
    
58.    
    
59.     private boolean isValid(Set<Character> failedSet, String val) {
    
60.         for (int i = 0; i < val.length(); i++) {
    
61.             if (failedSet.contains(val.charAt(i))) {
    
62.                 return false;
    
63.             }
    
64.         }
    
65.         return true;
    
66.     }
    
67.    
    
68.     private void addToFailedSet(Set<Character> failedSet, String val) {
    
69.         for (int i = 0; i < val.length(); i++) {
    
70.             failedSet.add(val.charAt(i));
    
71.         }
    
72.     }

复制代码

同timeout，应该有更快的解法
import java.util.*;

public class Solution {
   
        HashMap<Character ,Integer> map = null;
        public  List<String> findSubstrings(String input) {
            List<String> tmp = new ArrayList<>();
            List<String> res = new ArrayList<>();
            HashSet<Character> set = new HashSet<>();

            HashMap<Character ,Integer> map = new HashMap<>();

            for(int i=0;i<input.length();i++){
                map.put(input.charAt(i),i);
            }
            this.map = map;
            DFS(input,tmp,res,0,set);
            return res;
        }

        private void DFS(String s, List<String> tmp,List<String> res, int index,HashSet<Character> set){
            if(s.length()-index+tmp.size()<res.size()){
                return;
            }

            if(index==s.length()){
                if(res.size()<tmp.size()){
                    res.clear();
                    res.addAll(tmp);

                }else if(res.size()==tmp.size()){
                    if(getLen(res)>getLen(tmp)){
                        res.clear();
                        res.addAll(tmp);
                    }
                }
                return;
            }

            if(set.contains(s.charAt(index))){
                DFS(s,tmp,res,index+1,set);
                return;
            }
            Character x = s.charAt(index);

            int y = findNext(x,s,index,set);
            if(y!=-1){
                String tmpp = s.substring(index,y+1);
                tmp.add(s.substring(index,y+1));

                DFS(s,tmp,res,y+1,set);

                tmp.remove(tmp.size()-1);
            }

            set.add(x);
            DFS(s,tmp,res,index+1,set);
            set.remove(x);
        }

        int findNext(Character x,String s,int i,HashSet<Character> set){
            int res = i;
            int xx = map.get(x);
            while(res<s.length()&&res<xx){
                if(set.contains(s.charAt(res))){
                    res = -1;
                    break;
                }
                xx  = Math.max(xx, map.get(s.charAt(res)));
                res ++;
            }
            return res;
        }


        int getLen(List<String> res){
            int x = 0;
            for(int i=0;i<res.size();i++){
                x += res.get(i).length();
            }
            return x;
        }

   
}

wangweihust 发表于 2020-6-15 09:50
我有个想法：先loop一遍，得到一个right most index for each character array arr[26] (或者map), where a ...

我之前就是按照这个想法尝试去写，找到right most index..
变成了bb, eadcxede
然后我就不知道怎么去call了，对于eadcxede包含多个不同的char，所以可以再取substring，这样就可以取到a, cx, 对于cx，可以再substring,就可以取到c, x. 都是单独一个char，无法再继续，所以停止。。

这是我的分析，就是卡壳写不出来。。。

这个好像理解题意就比较费劲啊...

求大神们指导啊

我有个想法：先loop一遍，得到一个right most index for each character array arr[26] (或者map), where arr[i] represents the right most index of letter 'a'+i in the string S; then recursively call the method. For eg. "bbeadcxede", you will call the helper method with "bb", "eadcxede". Then implement your method based on simple rules to return a list of substring.   

这个网站怎么样啊，第一次遇到，跟leetcode, lintcode有啥不一样的吗

为什么example里的 substring不能是“b” 要是“bb”呢

wangweihust 发表于 2020-6-15 09:52
这个网站怎么样啊，第一次遇到，跟leetcode, lintcode有啥不一样的吗

不清楚哦 我也是在面经里面看到的

感觉题的描述有问题..
"bb"根据题意要短一点，铁定可以只取一个'b'啊..
然后为什么第一个例子里连'e'都没有，不是数目越多越好吗。

这题根据给定条件我感觉是做不了的。
如果条件都清楚，那么用dfs + memo O(n^2)就可以解决。

wbxzhr123 发表于 2020-6-15 12:58
感觉题的描述有问题..
"bb"根据题意要短一点，铁定可以只取一个'b'啊..
然后为什么第一个例子里连'e'都没 ...

是不是条件2的限制？