567.Permutation in String

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

題目描述

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⁴
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;
    }
};

Yen-Chi ChenSat, 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

Yen-Chi ChenSat, Feb 4, 2023

Javascritp

思路：

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

先記錄s1中各字母出現的次數（s1Map）
遍歷s2，尋找長度為s1.length的子字串，並記錄各字母出現的次數（s2Map）
比較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;
}

寫完還是看不懂吉神寫的，怎麼可以這麼簡潔…
MarsgoatFeb 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;
}

感恩彥吉大神教學
MarsgoatFeb 16, 2023

Reference

回到題目列表