google 电话面试一面（已获二面）

写了段代码 有错误指出来哈

1. pair<int,int> minDistance(string s,string t){
   
2. 
   
3. unordered_map<char,vector<int>> mp;
   
4. pair<int,int> disM1(-1,-1);
   
5. pair<int,int> disM2(-1,-1);
   
6. 
   
7. for(int i=0;i<s.size();i++){
   
8.          if(s[i]!=t[i]){
   
9.               mp[s[i]].push_back(i);
   
10.               if(mp.find(t[i])!=mp.end()){
    
11.                       if(disM1==make_pair(-1,-1)){
    
12.                              disM1=make_pair(mp[t[i]][0],i);
    
13.                                          }
    
14.                       for(int j=0;j<mp[t[i]].size();j++){
    
15.                                     if(t[mp[t[i]][j]]==s[i]){
    
16.                                                disM2=make_pair(mp[t[i]][j],i);
    
17.                                                return disM2;
    
18.                                                             }
    
19.                                                       }
    
20.                                                                }
    
21.                                                               }
    
22.                                                               }
    
23.                                                    return disM1;
    
24. }

复制代码

stellari 发表于 2015-9-23 17:39
我想应该是可以做到O(N)的，只要能够抓住字符数n=26n=26这个特点。比如开一个26x26的数组int P[26][26]
来 ...

我不是很熟悉，能否请教如何删除？

我可以想到O(n) time O(n) space的解法，不过O(1) space O(n) time就不知道怎么做了



补充内容 (2015-9-23 22:34):
一亩三分地论坛是不是有bug 明明插入了code 回复的时候就消失了

1. pair<int, int> swapIndex(string& s, string& t){
   
2.         unordered_map<string, int> location;
   
3.         pair<int, int> res{-1,-1};
   
4.         for(int i=0; i < s.size(); i++){
   
5.                 if(s[i] != t[i]) location[""+s[i]+t[i]] = i;
   
6.         }
   
7.         if(location.empty()) return res;
   
8.        
   
9.         // Check if the distance can be improved by 2
   
10.         for(int i=0; i < s.size(); i++){
    
11.                 if(s[i] != t[i] && location.find(""+t[i] + s[i]) != location.end()){
    
12.                         res.first = location.find(""+t[i] + s[i])->second;
    
13.                         res.second = i;
    
14.                         return res;
    
15.                 }
    
16.         }
    
17.        
    
18.         // Check if the distance can be improved by 1
    
19.         unordered_map<char, int> single;
    
20.         for(int i=0; i < s.size(); i++){
    
21.                 if(s[i] != t[i]) single[s[i]] = i;
    
22.         }
    
23.         for(int i=0; i < s.size(); i++){
    
24.                 if(s[i] != t[i] && single.find(t[i]) != single.end()){
    
25.                         res.first = single.find(t[i])->second;
    
26.                         res.second = i;
    
27.                         return res;
    
28.                 }
    
29.         }
    
30.         // No solution
    
31.         return res;
    
32. }

复制代码

1. pair<int,int> get_swap(string s, string t) {
   
2.     vector<int> tab[26];
   
3.     for (int i=0; i<s.length(); i++)
   
4.         tab[s[i]-'a'].push_back(i);
   
5.     pair<int,int> ans(-1, -1);
   
6.     for (int j=0; j<t.length(); j++) {
   
7.         if (s[j] == t[j] || tab[t[j]-'a'].size()==0) continue;
   
8.         for (int i=0; i<tab[t[j]-'a'].size(); i++) {
   
9.             int id = tab[t[j]-'a'][i];
   
10.             if (s[j] == t[id]) return make_pair(id, j);
    
11.             else if (s[id] != t[id]) ans = make_pair(id, j);
    
12.         }
    
13.     }
    
14.     return ans;
    
15. }

复制代码

不要说话 发表于 2015-9-23 22:33

其实对于定长的character set来说，这解法已经可以称O(1)内存了。single可以用一个int[26]代替，而location也可以用int[26][26]代替。

stellari 发表于 2015-9-23 23:20
其实对于定长的character set来说，这解法已经可以称O(1)内存了。single可以用一个int[26]代替，而locati ...

赞 细想的确是 可以用一个二维数组[26][26] 代替location, 一位数组[26]代替single 总体算下来是O(n) time O(1) space