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
|
|
