数据结构有关字符串的面试题 求解答

Question

第一个题是 有两个字符串 比如“aedfetdfer" "aed" 判断第二个字符串的字母是否在第一个字符串全出现了。。 第二个题是 有一个字符串"aefecverdfefg" 找出该字符串中只出现一次的第一个字母。。 感激不尽

Answer 1

建一张hash表，记录a-z
26个字母的出现次数
char
table[
26
]
;
第一题，假设第一个字符串为s1,第2个字符串为s2
for(
i
=
0
;
i
<
26
)
;
i
++)
table[
i
]
=
0
;
for(
i
=
0
;
i
<
strlen(
s1
)
;
i
++)
table[
s1[i]
-
'a'
]
++
;
for(
i
=
0
;
i
<
strlen(
s2
)
;
i
++
)
if(
table[
s2[i]
-
'a'
]
==
0
)
{
print(
"字母
%c
没有出现"
,
s2[i]
);
break;
}
if(
i
>=
strlen(
s2
)
)
print(
"字母全部出现"
);
复杂度应是
O(M+N)
，
M和N分别是s1和s2的长度
第二题更简单了：
for(
i
=
0
;
i
<
26
)
;
i
++)
table[
i
]
=
0
;
for(
i
=
0
;
i
<
strlen(
s1
)
;
i
++)
table[
s1[i]
-
'a'
]
++
;
for(
i
=
0
;
i
<
26
)
;
i
++)
if(
table[i]
==
1
)
print(
"只出现一次的字母:
%c"
,
table[i]
);