SNAPCHAT电面挂经

maktf 发表于 2016-9-8 22:43
求问楼主从面完到有消息用了多久啊？而且他家的店面到底是45分钟还是一个小时？

早上面的，下午就有消息了，问了一下内部的朋友，说最近SNAPCHAT在谈IPO，为了防止有人进去混股票，BAR高了很多，ANYWAY，MOVE FORWARD了

请问需要考虑顺序吗？输出是list吗？{GAT, DOC} 和 {DOC, GAT} 算几个？

因为顺序不重要，所以可以将INPUT STRING ARRAY 2里的string先sort，建个hashmap存sorted string对应原string
对sorted string建Trie,这样可以方便之后搜索

然后对INPUT STRING ARRAY 1, count each char in it，然后就是dfs找出所有可能组合啦

大概写了一个。 要backtrack input2 而不是input1

1. public List<List<String>> wordSearch (String[] input1, String[] input2) {
   
2.                 /*
   
3.                  * 题大概是这样，一个INPUT STRING ARRAY1 比如CAT, DOG，一个INPUT STRING ARRAY 2， 比如GAT, DOC, CD, GOAT, BAD, COOL
   
4.                  * 要求第一个INPUT ARRAY的字母必须全部用，而且每个字母只能用一次，求其能组合成的INPUT STRING ARRAY2里的单词组
   
5.                  * 比如上面这个例子，返回值会是{{GAT, DOC},{CD, GOAT}}
   
6.                  */
   
7.                 //edge cases
   
8.                 List<List<String>> ret = new ArrayList<>();
   
9.                 StringBuilder input1B = new StringBuilder();
   
10.                 for (String s : input1) {
    
11.                         char[] arr = s.toCharArray();
    
12.                         for (char ch : arr) {
    
13.                                 input1B.append(ch);
    
14.                         }
    
15.                 }
    
16.                 backtracking (ret, new ArrayList<String>(), 0 ,input1B.toString().toCharArray(), input2);
    
17.                 return ret;
    
18.         }
    
19.        
    
20.         private void backtracking (List<List<String>> ret, List<String> temp, int start, char[] input1, String[] input2) {
    
21.                 if (isAnagram(input1, temp)) {
    
22.                         ret.add(new ArrayList<>(temp));
    
23.                 } else {
    
24.                         for (int i = start; i < input2.length; i++) {
    
25.                                 temp.add(input2[i]);
    
26.                                 backtracking (ret, temp, i+1, input1, input2);
    
27.                                 temp.remove(temp.size()-1);
    
28.                         }
    
29.                 }
    
30.         }
    
31.        
    
32.         private boolean isAnagram (char[] str1, List<String> temp) {
    
33.                 int[] trie = new int[26];
    
34.                 for (char c : str1) {
    
35.                         trie[c-'A']++;
    
36.                 }
    
37.                 for (String s : temp) {
    
38.                         for (int i = 0; i < s.length(); i++) {
    
39.                                 trie[s.charAt(i)-'A']--;
    
40.                         }
    
41.                 }
    
42.                 for (int i : trie) {
    
43.                         if (i != 0) return false;
    
44.                 }
    
45.                 return true;
    
46.         }

复制代码

感觉没必要用trie...dfs + 剪枝可以把 hashmap<char, int> map l取array1 word总长度， 每次l-- int=0时 map.remove(char), l<array2 中word length时，return
想不出啥优化，等大牛>.

白丁117 发表于 2016-9-25 11:00
感觉没必要用trie...dfs + 剪枝可以把 hashmap map l取array1 word总长度， 每次l-- int=0时 map.remove(ch ...

lz说了用trie是因为被要求的，因为input2会被query很多次，trie是个比较合理的数据结构

如果不用trie的写了这么一个。用trie的还没想，一会儿想想。

1. public class Solution {
   
2.     private List<List<String>> res = new ArrayList<>();
   
3.     private List<String> tmpRes = new ArrayList<>();
   
4.     private int charSum = 0;
   
5.     private int[] charSet = new int[26];
   
6. 
   
7.     public List<List<String>> wordSearch(String[] input1, String[] input2) {
   
8.         // build charSet
   
9.         for(String word: input1) {
   
10.             for(char c: word.toCharArray()) {
    
11.                 charSet[c - 'A']++;
    
12.                 charSum++;
    
13.             }
    
14.         }
    
15. 
    
16.         wordSearchHelper(input2, 0, 0);
    
17.         return res;
    
18.     }
    
19. 
    
20.     private void wordSearchHelper(String[] input2, int pos, int count) {
    
21.         if(count > charSum) return;
    
22. 
    
23.         if(count == charSum) {
    
24.             int[] tmpCharSum = Arrays.copyOf(charSet, 26);
    
25.             for(String word: tmpRes) {
    
26.                 for(char c: word.toCharArray()) {
    
27.                     if (--tmpCharSum[c - 'A'] < 0) return;
    
28.                 }
    
29.             }
    
30.             res.add(new ArrayList<>(tmpRes));
    
31.             return;
    
32.         }
    
33. 
    
34.         for(int i = pos; i < input2.length; i++) {
    
35.             tmpRes.add(input2[i]);
    
36.             wordSearchHelper(input2, i + 1, count + input2[i].length());
    
37.             tmpRes.remove(tmpRes.size() - 1);
    
38.         }
    
39.     }
    
40. }

复制代码

如果是给定了input2，并且反复调用API给新的input1，我觉得可以先对input2做各种排列组合，得到一个key value pair，key是组合之后所有出现的字母sort之后的string，value是这个key对应的各种组合。然后每次给一个新的input1，先把input1里所有的字母sort后并成一个string（比如例子里的变成ACDGOT），然后直接去key value pair里找对应的组合就好啦。思想类似于anagram吧

ariesxiao 发表于 2016-9-8 11:50
我建立TRIE是因为面试官一直在引导我建TRIE。。他之前跟我说如果INPUT ARRAY 2是不变的，用户CALL我们的A ...

我觉得你被误导了，那如果input2也是变化的，怎么做？
而且trie不应该用在这个场景，trie的话，字母顺序就固定了，现在这个问题不需要固定