Google onsite

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

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

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

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

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

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

第一轮对dict建trie在target string很长的情况下还是有用的，比如原本4个string（aaab, aaac, aaad）需要遍历4遍 target，现在只需要遍历一遍了

请问一下第一题的题意： subsequence 是要求 dict 中的某个string 都必须依次出现在target string里吗？ 比如target是“zzabcdefg", dict是｛"zaf", "mzzabcdefg"｝结果是3吗？因为第二个string中有m，不是target的subsequence?

第四轮我怎么感觉follow up和原题没什么区别。是我理解错了题目吗？

1. public char findTheDifference(String s, String t) {
   
2.         int[] chs = new int[26];
   
3.         char[] ss = s.toCharArray();
   
4.         char[] tt = t.toCharArray();
   
5.         for (int i = 0; i < ss.length; i ++) {
   
6.             chs[ss[i] - 'a'] --;
   
7.             chs[tt[i] - 'a'] ++;
   
8.         }
   
9.         chs[tt[tt.length - 1] - 'a'] ++;
   
10.         for (int i = 0; i < 26; i ++) {
    
11.             if (chs[i] > 0) return (char)('a' + i);
    
12.         }
    
13.         return 'a';
    
14.     }

复制代码

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

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

KimiZJ 发表于 2016-12-15 01:41
第一题建立trie树的确有优化效果，但是对复杂度没有影响。然后susequence是要求word必须依次出现在targrt ...

差值n个字符都可以用相同的思路来做啊。我写了个差值两个字符的

1. public class Solution {
   
2.     public char[] differentChar(String s, String t) {
   
3.         int[] tmp = new int[26];
   
4.         for (int index = 0; index < s.length(); index ++) {
   
5.             tmp[s.charAt(index) - 'a'] ++;
   
6.             tmp[t.charAt(index) - 'a'] --;
   
7.         }
   
8.         tmp[t.charAt(t.length() - 2) - 'a'] --;
   
9.         tmp[t.charAt(t.length() - 1) - 'a'] --;
   
10.         char[] res = new char[2];
    
11.         int resIndex = 0;
    
12.         for (int index = 0; index < 26; index ++) {
    
13.             if (tmp[index] == -1) {
    
14.                 res[resIndex ++] = (char)(index + 'a');
    
15.             } else if (tmp[index] == -2) {
    
16.                 res[0] = (char)(index + 'a');
    
17.                 res[1] = (char)(index + 'a');
    
18.             }
    
19.         }
    
20.         return res;
    
21.     }
    
22.     public static void main(String[] args) {
    
23.         Solution sol = new Solution();
    
24.         char[] res = sol.differentChar("daabc", "bzcaade");
    
25.         System.out.println(res[0] + ", " + res[1]);
    
26.     }
    
27. }

复制代码

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

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

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

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