CTCI Ch.1.2 检查排列

Question

问候，节日快乐，

我的问题涉及“Cracking The Coding Interview”第 6 版中的问题“1.2 Check Permutation”

当我们比较这两个字符串时，我们会检查数组中是否有任何值小于 0。这表明我们的两个字符串的字符数不同。但是，比较不应该是 !== 0 而不是 < 0 吗？这将捕获字符的过多和不足。我没有在勘误表或任何相关搜索结果中看到它。

下面是提供的代码解决方案。（本人主要从事JS工作，所以可能是我看错了代码）

非常感谢。

boolean permutation(String s, String t) {
    if (s.length() != t.length()) {
        return false;
    }

    int[] letters = new int[128]; 

    char[] s_array = s.toCharArray();
    for (char c : s_array) {
            letters[c]++;
    }

    
    for (int i = 0; i < t.length(); i++) {
        int c = (int) t.charAt(i); 
        letters[c]--;
        if (letters[c] < 0) { // this is the line in question
            return false;
        }
    }
    return true;
}

Answer 1

!= 0 的比较只有在计算完所有差异后才有意义。代码的结构方式允许早期检测。

第一个测试是 s.length() != t.length()。一旦代码通过它，我们就知道字符数是相等的。这意味着 - 如果字符串不是排列 - 有一个字符在 t 中出现的次数多于在 s 中出现的次数。一旦找到这样的字符，我们就得出结论 t 不是排列。

CTCI Ch.1.2 检查排列

CTCI Ch.1.2 Check Permutation

javascript

algorithm

computer-science

permutation

data-structures