0 题目来源

力扣《程序员面试金典》

1 本题涉及到的知识点

字符串、哈希、排序、C++（map、unorder_map）、降低时间复杂度的一些手段。

1. map和unordered_map的异同：

• 两者的使用方法一致
• 内部组织方式不同，map使用红黑树实现，内部有序；unordered_map使用哈希表实现，内部无序。
• unordered_map在一些算法比赛的编译环境下不支持，慎用。

1. map和unordered_map的使用方法：

• 首先要**#include<map>**或**#include<unordered_map>**
• 然后进行定义：**map<char,int>mp//表示char到int的map**
• 之后可以直接使用：**mp['a']++//mp中的各项自动初始化是0，可以直接使用**
• 使用for循环对map进行遍历：**for(int i=0;i<mp.size();i++)//可以直接使用mp[i]来表示map中的每一项**。
• 在map中,只要对某一个数据进行过访问(包括判断该数据是否存在),都会导致map.size()+1。

1. 降低时间复杂度的一些手段：

• 在面对一个问题时，首先可以用一个简单的判断来解决大部分的情况；之后再完成其他的复杂情况。这样可以使得大部分的情况得以在较低的时间复杂度下解决。

  2 题目描述

  给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
  说明：

• 0 <= len(s1) <= 100

• 0 <= len(s2) <= 100

  3 输入与输出格式

  无，力扣略了

  4 样例

  示例 1：
  输入: s1 = “abc”, s2 = “bca”
  输出: true
  示例 2：
  输入: s1 = “abc”, s2 = “bad”
  输出: false

  5 分析与代码

  方法1 哈希表（map/unordered_map）

  这种方法是比较合适的一种方法，使用c++的map或者unordered_map作为哈希表。（unordered_map在一些算法竞赛中不能使用，因此可以用map）。
  降低时间复杂度的方法：首先对两个字符串的长度是否相等进行判断，可以快速得出答案，便于降低时间复杂度。
  之后，对s1进行遍历，对map的对应位置进行++操作；然后对s2进行遍历，对map的对应位置进行—操作。
  最后，遍历map，判断其中是否有非零元素，有的话则输出false，否则输出true。
  代码：

  class Solution {
  public:
    bool CheckPermutation(string s1, string s2) {
        map<char,int>mp;
        if(s1.size()!=s2.size())
            return false;
        for(int i=0;i<s1.size();i++)
            mp[s1[i]]++;
        for(int i=0;i<s2.size();i++)
            mp[s2[i]]--;
        for(int i=0;i<mp.size();i++)
        {
            if(mp[i]!=0)
                return false;
        }
        return true;
    }
  };

  方法2 排序：

  先对s1和s2进行排序，然后再直接比较s1和s2是否相等。
  代码：

  class Solution {
  public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(),s1.end());
        sort(s2.begin(),s2.end());
        return s1==s2;
    }
  };