算法实战——字符串（二）

第一题：写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

判断两个字符串是否互为变位词，若区分大小写，考虑空白字符时，直接来理解可以认为两个字符串的拥有各不同字符的数量相同。对于比较字符数量的问题常用的方法为遍历两个字符串，统计其中各字符出现的频次，若不等则返回false

Python

class Solution:
 """
 @param s: The first string
 @param b: The second string
 @return true or false
 """
 def anagram(self, s, t):
 return collections.Counter(s) == collections.Counter(t)

C++

class Solution {
public:
 /**
 * @param s: The first string
 * @param b: The second string
 * @return true or false
 */
 bool anagram(string s, string t) {
 if (s.empty() || t.empty()) {
 return false;
 }
 if (s.size() != t.size()) {
 return false;
 }
 int letterCount[256] = {0};
 for (int i = 0; i != s.size(); ++i) {
 ++letterCount[s[i]];
 --letterCount[t[i]];
 }
 for (int i = 0; i != t.size(); ++i) {
 if (letterCount[t[i]] != 0) {
 return false;
 }
 }
 return true;
 }
};

源码分析

1. 两个字符串长度不等时必不可能为变位词(需要注意题目条件灵活处理)。
2. 初始化含有256个字符的计数器数组。
3. 对字符串 s 自增，字符串 t 递减，再次遍历判断letterCount数组的值，小于0时返回false.

在字符串长度较长(大于所有可能的字符数)时，还可对第二个for循环做进一步优化，即t.size() > 256时，使用256替代t.size(), 使用i替代t[i].

第二题：比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母

既然不是类似 strstr 那样的匹配，直接使用两重循环就不太合适了。题目中另外给的条件则是A和B都是全大写单词，理解题意后容易想到的方案就是先遍历 A 和 B 统计各字符出现的频次，然后比较频次大小即可。嗯，祭出万能的哈希表。

Python

Python 的dict就是hash， 所以python 在处理需要用到hash的地方非常方便。

import collections
class Solution:
 def compare_strings(self, A, B):
 # return a dict with default value set to 0
 letters = collections.defaultdict(int)
 for a in A:
 letters[a] += 1
 for b in B:
 if b not in letters:
 return False
 elif letters[b] <= 0:
 return False
 else:
 letters[b] -= 1
 return True

源码解析

1. 异常处理，B 的长度大于 A 时必定返回false, 包含了空串的特殊情况。
2. 使用额外的辅助空间，统计各字符的频次。

复杂度分析

遍历一次 A 字符串，遍历一次 B 字符串，时间复杂度最坏 $O(2n)$, 空间复杂度为 $O(26)$.

C++

class Solution {
public:
 /**
 * @param A: A string includes Upper Case letters
 * @param B: A string includes Upper Case letter
 * @return: if string A contains all of the characters in B return true
 * else return false
 */
 bool compareStrings(string A, string B) {
 if (A.size() < B.size()) {
 return false;
 }
 const int AlphabetNum = 26;
 int letterCount[AlphabetNum] = {0};
 for (int i = 0; i != A.size(); ++i) {
 ++letterCount[A[i] - 'A'];
 }
 for (int i = 0; i != B.size(); ++i) {
 --letterCount[B[i] - 'A'];
 if (letterCount[B[i] - 'A'] < 0) {
 return false;
 }
 }
 return true;
 }
};

源码解析

1. 异常处理，B 的长度大于 A 时必定返回false, 包含了空串的特殊情况。
2. 使用额外的辅助空间，统计各字符的频次。