SNAPCHAT电面挂经

题大概是这样，一个INPUT STRING ARRAY1 比如CAT, DOG，一个INPUT STRING ARRAY 2， 比如GAT, DOC, CD, GOAT,

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

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

先搜索，但是做来做去都写的不太对，然后果然电面就挂了
求大牛给完整思路和代码

谢了

如果不用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. }

复制代码

大概写了一个。 要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.         }

复制代码

这不是word search two 么？

这个题目用Backtracking可以做

第一个array只有total count是有用信息，数一遍就好了。
第二个array那里可以预处理一下把count先数好，把有字母occurrence大于array 1的total count的那些单词直接扔掉。
然后就类似没有重复的combination sum做个DFS就行了，只是DFS是26个target，combination sum是一个target。

不知道你为什么要建trie，这个问题里完全没有前缀结构啊...

hxtang 发表于 2016-9-8 11:07
第一个array只有total count是有用信息，数一遍就好了。
第二个array那里可以预处理一下把count先数好，把 ...

我建立TRIE是因为面试官一直在引导我建TRIE。。他之前跟我说如果INPUT ARRAY 2是不变的，用户CALL我们的API只是不断的给我们INPUT ARRAY 1，然后返回结果

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

我觉得他的意思是说input array 2因为可能被用多次，所以尽量多做点预处理....预处理不一定是建trie...

好题，preprocessing array2得到List<Map<Character, Integer>>,  相当于coins； array1得到Map<Character, Integer> 相当于target； 然后dfs求coins组合

我的理解是建个HashMap<Character, Integer> map, 先记录string1每个字母出现个数，然后再遍历string2的每个单词，if（map.get(s2.charAt(i))<1)则表示这个单词不符合。我不是很理解为什么要用trie树做，trie树如果是prefix问题还可以，可是这个。。

随手写了一段代码，楼主给出的测试数据是能通过的，其他的没有测过。如果有bug请通知我。

1. class Solution {
   
2. public:
   
3.         vector<vector<string>> snapchat(vector<string> input1, vector<string> input2) {
   
4.                 total = 0;
   
5.                 for (auto s : input1) {
   
6.                         for (auto c : s) {
   
7.                                 count[c - 'A']++;
   
8.                                 total++;
   
9.                         }
   
10.                 }
    
11.                 vector<string> curr;
    
12.                 dfs(input2, 0, 0, curr);
    
13.                 return result;
    
14.         }
    
15. 
    
16.         void dfs(vector<string>& words, int pos, int occ, vector<string>& curr) {
    
17.                 if (occ == total) {
    
18.                         result.push_back(curr);
    
19.                         return;
    
20.                 }
    
21.                 for (int i = pos; i < words.size(); i++) {
    
22.                         string word = words[i];
    
23.                         bool flag = true;
    
24.                         for (auto c : word) {
    
25.                                 count[c - 'A']--;
    
26.                                 if (count[c - 'A'] < 0) flag = false;
    
27.                                 occ++;
    
28.                         }
    
29.                         if (flag) {
    
30.                                 curr.push_back(word);
    
31.                                 dfs(words, i + 1, occ, curr);
    
32.                                 curr.pop_back();
    
33.                         }
    
34.                         for (auto c : word) {
    
35.                                 count[c - 'A']++;
    
36.                                 occ--;
    
37.                         }
    
38.                 }
    
39.         }
    
40. 
    
41. private:
    
42.         unordered_map<char, int> count;
    
43.         vector<vector<string>> result;
    
44.         int total;
    
45. }

复制代码

求问楼主从面完到有消息用了多久啊？而且他家的店面到底是45分钟还是一个小时？