567.Permutation in String
===

###### tags: `Medium`,`String`,`Hash Table`,`Two Pointers`,`Sliding Window`

[567. Permutation in String](https://leetcode.com/problems/permutation-in-string/)

### 題目描述

Given two strings `s1` and `s2`, return `true` *if* `s2` *contains a permutation of* `s1`, *or* `false` *otherwise.*

In other words, return `true` if one of `s1`'s permutations is the substring of `s2`.

### 範例

**Example 1:**

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

**Example 2:**

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

**Constraints**:

* 1 <= `s1.length`, `s2.length` <= 10^4^
* `s1` and `s2` consist of lowercase English letters.

### 解答
#### C++

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1 = s1.size(), n2 = s2.size();
        vector<int> cnt1(26, 0), cnt2(26, 0);
        for (auto c : s1) {
            cnt1[c - 'a']++;
        }
        for (int i = 0; i < n2; i++) {
            auto c = s2[i];
            cnt2[c - 'a']++;
            if (i >= n1) cnt2[s2[i - n1] - 'a']--;
            if (cnt1 == cnt2) return true;
        }
        return false;
    }
};

> [name=Yen-Chi Chen][time=Sat, Feb 4, 2023]

#### Python

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1, n2 = len(s1), len(s2)
        c1, c2 = Counter(s1), Counter(s2[:n1])
        if c1 == c2: return True
        for i in range(n1, n2):
            c2[s2[i]] += 1
            c2[s2[i - n1]] -= 1
            if c1 == c2: return True
        return False

> [name=Yen-Chi Chen][time=Sat, Feb 4, 2023]

#### Javascritp
##### 思路：
一開始耍腦殘把`s1`的字母所有排列組合都列出來然後丟到`s2`去比對。
其實不用管`s1`的組合，只要找`s2`中相同長度的子字串，其中有`s1`的所有字母且各字母數一樣即可。
例：
`s1 = aabc`
`s2 = bacadbe`
`s2`的子字串中只要符合長度與`s1`相同且有2個`a`、1個`b`、1個`c`，那就一定是`s1`的排列組合之一。

1. 先記錄`s1`中各字母出現的次數（`s1Map`）
2. 遍歷`s2`，尋找長度為`s1.length`的子字串，並記錄各字母出現的次數（`s2Map`）
3. 比較`s1Map`與`s2Map`中各字母出現的次數是否相同

使用slinding window就不用每次都重新計算`s2Map`，只要把最左邊的字母刪掉，再把最右邊的字母加進去即可。

function checkInclusion(s1, s2) {
  // 紀錄s1中每個字母出現的次數
  const s1Map = new Map();
  for (const char of s1) {
    s1Map.set(char, s1Map.get(char) + 1 || 1);
  }

  const s2Map = new Map();
  let left = 0; // 紀錄從何處開始比對
  for (let i = 0; i < s2.length; i++) {
    if (s1Map.has(s2[i])) {
      s2Map.set(s2[i], s2Map.get(s2[i]) + 1 || 1);

      // 當s2Map中單一字母的數量大於s1Map中單一字母的數量時，把最左邊的字母刪掉
      while (s2Map.get(s2[i]) > s1Map.get(s2[i])) {
        s2Map.set(s2[left], s2Map.get(s2[left]) - 1);
        left++;
      }

      // 當s2Map中的字母數量等於s1Map中的字母數量時，檢查各字母的數量是否相同
      if (s2Map.size === s1Map.size) {
        let isSame = true;
        for (const [key, value] of s1Map) {
          if (s2Map.get(key) !== value) {
            isSame = false;
            break;
          }
        }

        if (isSame) return true;
      }
    } else {
      // 出現不一樣的字母時，直接清空s2Map
      s2Map.clear();
      left = i + 1;
    }
  }

  return false;
}

> 寫完還是看不懂吉神寫的，怎麼可以這麼簡潔...
> [name=Marsgoat][time=Feb 16, 2023]

吉神教學版
> 吉神：我們其實只需要用一個s1大小的sliding window在s2上掃過去就好

function checkInclusion2(s1, s2) {
  const s1Map = new Array(26).fill(0);
  const s2Map = new Array(26).fill(0);
  for (const char of s1) {
    s1Map[char.charCodeAt() - 97]++;
  }
  const n = s1.length;

  for (let i = 0; i < s2.length; i++) {
    s2Map[s2.charCodeAt(i) - 97]++;

    if (i >= n) {
      s2Map[s2.charCodeAt(i - n) - 97]--;
    }

    if (s1Map.join() === s2Map.join()) return true;
  }

  return false;
}

> 感恩彥吉大神教學
> [name=Marsgoat][time=Feb 16, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)