Codewars Isogram问题代码优化及时间复杂度降低方案咨询
题目说明
Isogram指不存在重复字母的单词,无论重复是连续还是非连续的。需要实现一个函数,判断仅包含字母的输入字符串是否为Isogram,约定空字符串属于Isogram,判断时忽略字母大小写。
测试用例:
"Dermatoglyphics" --> true "aba" --> false "balLoon" --> false
现有代码存在的问题
你给出的双层循环实现首先存在逻辑错误:return true 放在了内层循环体内,会导致只要第一次比较两个不同字符就直接返回真,完全无法正确判断后续是否有重复字符,比如输入"aba"会被误判为true。其次该实现时间复杂度为O(n²),字符串长度较长时效率很低,此外直接用ASCII码±32判断大小写兼容性较差,更推荐用标准库的大小写转换函数。
优化方案
可以将时间复杂度降低到O(n),因为输入仅包含字母,一共只有26个英文字母,我们可以用固定大小的存储空间记录字符是否出现过,空间复杂度为O(1),属于该问题的最优解。
方案1:布尔数组实现
#include <cctype> #include <string> using namespace std; bool isIsogram(string s) { bool seen[26] = {false}; for (char c : s) { char lower_c = tolower(c); int idx = lower_c - 'a'; if (seen[idx]) { return false; } seen[idx] = true; } return true; }
方案2:位运算实现(更省空间)
用一个int整数的低26位分别对应26个字母是否出现,仅需4字节存储空间:
#include <cctype> #include <string> using namespace std; bool isIsogram(string s) { int mask = 0; for (char c : s) { int idx = tolower(c) - 'a'; if (mask & (1 << idx)) { return false; } mask |= (1 << idx); } return true; }
两种优化方案都只需要遍历字符串一次,时间复杂度O(n),相比原双层循环效率提升非常明显,且逻辑更简洁,出错概率低。
内容的提问来源于stack exchange,提问作者pekking
相关产品推荐
相关产品推荐

