You need to enable JavaScript to run this app. Codewars Isogram问题代码优化及时间复杂度降低方案咨询
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.17 19:06:04