Swift优化：判断短字符串字符是否可由长字符串字符无重复组成

你的现有排序遍历方案虽能实现需求，但时间复杂度较高（排序阶段为O(n log n)，后续每次查找、删除操作都是线性耗时）。更高效的思路是统计字符出现频率，借助哈希表（字典）完成快速验证，整体时间复杂度可降至O(n + m)（n、m分别为两个字符串的长度）。

优化思路 #

1. 快速失败判断：若目标字符串（Word B）长度大于原字符串（Word A），直接返回false——原字符串不可能提供足够多的字符。
2. 统计原字符串字符频率：用字典记录Word A中每个字符的出现次数。
3. 验证目标字符串：遍历Word B的每个字符，在字典中检查：
   • 若字符不存在或剩余次数为0，返回false
   • 若存在，将对应字符的计数减1
4. 遍历完成后返回true

Swift 代码实现 #

func canSpell(_ wordB: String, using wordA: String) -> Bool {
    // 快速失败：wordB更长直接返回false
    guard wordB.count <= wordA.count else { return false }
    
    // 统计wordA的字符频率
    var charCount = [Character: Int]()
    for char in wordA {
        charCount[char, default: 0] += 1
    }
    
    // 验证wordB的每个字符
    for char in wordB {
        guard let count = charCount[char], count > 0 else {
            return false
        }
        charCount[char] = count - 1
    }
    
    return true
}

// 测试示例
let wordOne = "battle"
let wordTwo = "table"
print(canSpell(wordTwo, using: wordOne)) // 输出 true

效率优势说明 #

• 字符统计和遍历均为线性时间操作，整体复杂度O(n + m)，远优于排序方案的O(n log n + m log m + m*n)
• 字典的查找、更新操作平均时间复杂度为O(1)
• 空间复杂度为O(1)（字符集大小固定，比如英文字母仅26个，即使是常用Unicode字符，数量也有限）

内容的提问来源于stack exchange，提问作者Henry McCreight