令人头大的字符串—算法处理
这是无量测试之道的第194篇原创
引言：
字符串可以看成是字符组成的数组。由于字符串是程序里经常需要处理的数据类型，因此有很多针对字符串处理的题目，以下是一些常见的类型。
第一题：第一个只出现一次的字符
题解：
- 遍历字符串数组
- 然后运用字典的特性，其中，key 为 character， value 为 character 出现的次数【比如 a 为 key，则 map[a] == 2】
- 最后返回 value == 1的 key 即是答案
code：
func firstUniqChar(_ s: String) -> Character {
var map = [Character:Int]()
for c in s {
map[c] = (map[c] ?? 0) + 1
}
for c in s {
if map[c] == 1 {
return c
}
}
return Character(" ")
}
为什么还要通过 for 循环遍历一次 s 然后去取第一个 map[c] == 1的 key ? 答：是因为 map 是乱序的，所以需要通过字符串s的顺序来返回第一次出现的字符
下面的代码就是错误的：因为 map 是乱序的
class Solution {
func firstUniqChar(_ s: String) -> Character {
var map = [Character:Int]()
for c in s {
map[c] = (map[c] ?? 0) + 1
}
for d in map {
if d.value == 1 {
return d.key
}
}
return Character(" ")
}
}
第二题：字符串比较：有效的字母异位词
题解：
我们可以利用哈希表或者数组统计两个字符串数组中每个字符出现的频次，若频次相同，则说明它们包含的字符完全相同
- 遍历字符串数组
- 然后运用字典的特性，其中，key 为 character， value 为 character出现的次数
- 遍历字符数组
s，然后 map[c] += 1 - 遍历字符数组
t，然后 map[c] -= 1 - 最后遍历 map，只要 map 的 value 有一个值不为 0 直接返回 false
code：
我使用的是字典
func isAnagram(_ s: String, _ t: String) -> Bool {
if s.count != t.count { return false }
var map = [Character:Int]()
for c in s {
map[c] = (map[c] ?? 0) + 1
}
for c in t {
map[c] = (map[c] ?? 0) - 1
}
for value in map {
if value.value != 0 {
return false
}
}
return true
}
优化：
先看下 C++ 的实现方式
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
vector<int> counts(26, 0);
for (int i = 0; i < s.length(); ++i) {
++counts[s[i]-’a’];
--counts[t[i]-’a’];
}
for (int i = 0; i < 26; ++i) {
if (counts[i]) {
return false;
}
}
return true;
}for (int i = 0; i < s.length(); ++i) {
++counts[s[i]-’a’];
--counts[t[i]-’a’];
}上面的这段代码将两次 for 循环写在一起了，减少了一倍的遍历次数。但是 swift 的语言特性的原因，没办法写在一起。大家看下自己熟悉的语言是否可以写成 C++ 的这个解法。
end
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号