a********r 发帖数: 218 | 1 给你两个string, 返回最早重复的那个字母的最小的index
要求优化时间复杂度(两个loop肯定不行)
abbbce
ddddab
return 0 (a, b repeated, a's index is 0 in first string)
=========================
a
b
return -1 (no repeated)
=============================
aaaaaxxxy
ccx
return 2 (x repeated, x's index is 2 in second string ) | d****g 发帖数: 62 | 2 O(m+n) using hash table
【在 a********r 的大作中提到】 : 给你两个string, 返回最早重复的那个字母的最小的index : 要求优化时间复杂度(两个loop肯定不行) : abbbce : ddddab : return 0 (a, b repeated, a's index is 0 in first string) : ========================= : a : b : return -1 (no repeated) : =============================
| a********r 发帖数: 218 | 3 The key is a, b, c, d, e ....? 但字母有重复,我试了
C++ map, unordered_map,都不允许有重复的key
【在 d****g 的大作中提到】 : O(m+n) using hash table
| j*r 发帖数: 23 | 4 you only need to put them to has table once, i.e. when you see them the
first time. | d****g 发帖数: 62 | 5 enjoy...
int func(const string &s1, const string &s2)
{
const int sz1=s1.size(), sz2=s2.size();
if(sz1==0 || sz2==0)
return -1;
int m[26], ret=-1;
memset(m, -1, sizeof(m));
for(int i=0; i
if(m[s1[i]-'a']<0)
m[s1[i]-'a']=i;
for(int i=0; ret!=0 && i
if(m[s2[i]-'a']>=0 && (ret<0 || ret>min(i, m[s2[i]-'a'])))
ret=min(i, m[s2[i]-'a']);
return ret;
}
【在 a********r 的大作中提到】 : The key is a, b, c, d, e ....? 但字母有重复,我试了 : C++ map, unordered_map,都不允许有重复的key
|
|