G家实习电面挂经

catinclay 发表于 2016-11-9 23:43
这不就是楼主的方法吗...貌似面官觉得复杂度太高?

即使用O(|s|)时间判断字典中每个单词w是否是s的subsequence，那么总时间O(|s|*|dict|)也会有很多浪费的地方。例如当字典中2个单词有公用prefix的时候，这时公共的prefix只需要在s中查找一次，所以尤其是s很长时浪费就更严重。我觉得这也许是面试官提出的s很长怎么办。关键是把字典中的单词分别处理是不行的，这样的后果是每当s增加时，总复杂度增加和|dict|成正比。

为了避免重复prefix matching，还是应该将字典中所有长度不超过|s|的单词建立一个Trie，我写了一下在30层。

补充内容 (2016-11-10 03:55):
例如s="zzzzzzzzzzzzzzzzzzzzzzabcd", dict = { "abc", "abd" }. 那么公共prefix "ab"不要字典中的每个单词都在s中调用firstIndexOf来查找。

楼主不要灰心， 加油加油！

Pat pat~~LZ 说实在的，这题要是让我临场限时做真的很不容易。在场下总是有足够的时间慢慢想。。。

好题目。

zzgzzm 发表于 2016-11-10 03:41
即使用O(|s|)时间判断字典中每个单词w是否是s的sunsequence，那么总时间O(|s|*|D|)也会有很多浪费的地方 ...

直接用hashmap存所有prefix的last index in original string会不会比较快?

catinclay 发表于 2016-11-10 05:33
直接用hashmap存所有prefix的last index in original string会不会比较快?

楼主不是用这种方法了么，面试官说不行。

primbo 发表于 2016-11-10 05:41
楼主不是用这种方法了么，面试官说不行。

楼主是只记字符的位置吧 我是说记所有prefix的位置

感觉双指针就可以了，贴个代码
public class FindString {
        public String findString(String s, List<String> dict) {
                int len = Integer.MAX_VALUE;
                String res = "";
                for (String word : dict) {
                        if (dist(s, word) < len) {
                                len = dist(s, word);
                                res = word;
                        }
                }
                return res;
        }
       
        // traverse dictionary
        private int dist(String s1, String s2) {
                int i = 0;
                int j = 0;
                while (i < s1.length() && j < s2.length()) {
                        if (s1.charAt(i) != s2.charAt(j)) {
                                i++;
                        } else if (s1.charAt(i) == s2.charAt(j)) {
                                i++;
                                j++;
                        }
                }
                if (j == s2.length())
                        return s1.length() - s2.length();
                else
                        return Integer.MAX_VALUE;
        }
}

你这个跟楼主的解法没有区别，跟楼上提出的解法类似的复杂度。 我一上来的idea就是读一遍S，然后存下map<char, freq> 跟map<char, minHeap<index>>，然后对dict里面的每一个word走一遍就行了，这个方法是线性的时间，线性的空间，应该是最优的时间，空间或许还有提升空间，不过我暂时看不到降低空间到O(1)的可能性

补充内容 (2016-11-10 06:49):
不对，由于无法提前build min heap，所以这个过程取决于重复最多的char的次数，但是有足够的操作空间，比如minheap size肯定不超过dict里面最长word等剪纸方法。这样看来，最worse的情况S: nlogn + dict：线性

已注销用户-D3F3 发表于 2016-11-10 06:46
你这个跟楼主的解法没有区别，跟楼上提出的解法类似的复杂度。 我一上来的idea就是读一遍S，然后存下map 跟 ...

我的想法是让后面的string可以利用前面的结果
假如你知道abc的c最后出现在index = 50的位置,
那对于abcd就可以从index = 50的地方开始找d.

做完这两个之后你就会在map里面有a, ab, abc, abcd四个prefix的结尾index.
对于下一个string(假设是abce) 我们先看abce有没有存在在map里, 如果没有就往前找abc,
此时找到了(map.get("abc") = 50 ), 就从50的位置开始找e.

这方法基本跟trie差不多, 但感觉实现起来更简单些.