原题描述

给定两个字符串，请编写程序，确定一个字符串的字符重新排列之后，能否成为另外一个字符串

算法

Tips：应询问一些关于变位词的细节

• 是否区分大小写， 即 God和dog是否为变位词？
• 在比较的字符串是否考虑空白（空格）？

Idea：

1. 若两个字符串长度不同，则一定不是变位词
2. 若相同，则有两种方案，即排序和统计
   • 排序：两个变位词排序后的字符串是相等的；优点：清晰，简单，移动；缺点：效率不是最优
   • 统计：变位词的字符数相同，可以使用hash表进行统计每个字符出现的次数，其效率最优

Algo：

1. 判断两个字符串的长度，若不同则直接退出，返回false
2. 声明用于统计的hash表  [ASCII字符集---数组替代Hash表]
3. 循环统计其中一个字符串的每个字符的出现次数
4. 使用抵消法遍历另一个字符串：
		判断当前字符的统计次数是否为0，并统计次数自减
			若为0，则退出，返回false
5. 成功遍历完成，则返回true

C++代码

bool permutation(string s, string p) {
  if (s.length() != p.length()) {
    return false;
  }

  int counts[256];

  for (int i = 0; i < s.length(); i++) {
    counts[s[i]]++;
  }

  for (int i = 0; i < p.length(); i++) {
    if (counts[p[i]]-- == 0) {
      return false;
    }
  }

  return true;
}

Bug Free Procedure

• 2017.01.15 Bingo！！！一次性AC
• 2017.01.16 Bingo！！！一次性AC