LeetCode + 《剑指Offer II》刷题笔记。

哈希表

032. 有效的变位词

剑指 Offer II 032. 有效的变位词

排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;
        if(s==t) return false;
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());
        return s==t;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        if(s.equals(t)) return false;
        char[] str1=s.toCharArray();
        char[] str2=t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1,str2);
    }
}

时间复杂度：O(nlogn)，其中 n 为 s 的长度。排序的时间复杂度为 O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)，最多需要执行两次字符串比较，因此总体时间复杂度为O(nlogn+2*n)=O(nlogn)。

空间复杂度：O(logn)。排序需要 O(logn) 的空间复杂度。注意，在某些语言（比如 Java & JavaScript）中字符串是不可变的，因此我们需要额外的 O(n) 的空间来拷贝字符串。但是我们忽略这一复杂度分析，因为：

  • 这依赖于语言的细节；
  • 这取决于函数的设计方式，例如，可以将函数参数类型更改为 char[]。

只考虑英文字母

只考虑英文字母，则用数组模拟哈希表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;
        if(s==t) return false;
        vector<int> counts(26);
        for(char ch:s){
            counts[ch-'a']++;
        }
        for(char ch:t){
            if(counts[ch-'a']==0) return false;
            counts[ch-'a']--;
        }
        return true;
    }
};

借鉴作者的答案代码：

  • 用for each遍历代替for循环

  • 第二个for each遍历中的设计很巧妙，这样就可以直接返回false，循化外就可以直接返回true，不需要再遍历一次哈希表一一检查是否为0。

时间复杂度：O(n)

空间复杂度：O(1)

考虑非英文字母

如果考虑非英文字母(输入字符串包含 Unicode 字符)，则用真正的哈希表HashMap。

注意 Unicode 一个字符可能对应多个字节，不同语言对于字符串读取处理的方式是不同的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.length()!=t.length()) return false;
        if(s==t) return false;
        unordered_map<char,int> counts;
        for(char ch:s){
            counts[ch]++;
        }
        for(char ch:t){
            if(counts[ch]==0) return false;
            counts[ch]--;
        }
        return true;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)