LeetCode: 567-Permutation in String 解題紀錄

Last Updated on 2022-02-11 by Clay

題目

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 <= 104
• s1 and s2 consist of lowercase English letters.

題目給定兩個輸入字串，我們要判斷的 s2 是否包含跟 s1 『結構相同』的子字串。

比方說 Example 1，s1 為 ab，那麼實際上 s2 不論是包含 ab 還是 ba 都算是包含，我們要回傳 true；然後若是僅包含像是 axb 這樣無連接的子字串則不算。

---

解題思路

首先我先建立 v1 以及 v2 兩個陣列，並將 0 – 25 共 26 個索引欄位視為 a – z 的數量。

初始全部都為零，接著要計算 s1 中的字元包含多少次，比方說 a 出現了兩次，那麼 v1[0] = 2 ….. 依此類推。

接著使用 s2 計算同樣長度的 v2，每次往前推移一個位置時，就需要將最開頭的字元去掉，隨時保持著跟 s1 長度一樣的字元數，也同時比較 v1 是否與 v2 相同（Python3 的程式由於個人強迫症因素改成 l1 及 l2）。相同的情況自然是直接停止計算，返回 true。

反之一直到 s2 遍歷完成也沒有匹配的情況，則在程式尾端返回 false。

複雜度

由於存取的空間固定是 52 個位置，故我還是將其視為 O(1)。

Time Complexity	O(n)
Space Complexity	O(1)

C++ 範例程式碼

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        // Base case
        if (s1.size() > s2.size()) return false;
        
        // Init
        vector<int> v1(26, 0);
        vector<int> v2(26, 0);
        
        // Prepare v1 and v2
        for (int i=0; i<s1.size(); ++i) {
            ++v1[int(s1[i])-97];
            ++v2[int(s2[i])-97];
        }
        
        // First match
        if (v1 == v2) return true;
        
        // For-loop match
        for (int i=0; i<s2.size()-s1.size(); ++i) {
            --v2[int(s2[i])-97];
            ++v2[int(s2[i+s1.size()])-97];
            
            if (v1 == v2) return true;
        }
        
        // If not match case, return false
        return false;
    }
};

Python 範例程式碼

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        # Base case
        if len(s1) > len(s2): return False
        
        # Init
        l1 = [0 for _ in range(26)]
        l2 = [0 for _ in range(26)]
        
        # Prepare v1 and v2
        for i in range(len(s1)):
            l1[ord(s1[i])-97] += 1
            l2[ord(s2[i])-97] += 1
        
        # First match
        if l1 == l2: return True
        
        # For-loop match
        for i in range(len(s2)-len(s1)):
            l2[ord(s2[i])-97] -= 1
            l2[ord(s2[i+len(s1)])-97] += 1
            
            if l1 == l2: return True
        
        # If not match case, return false
        return False

---

References

• https://leetcode.com/problems/permutation-in-string/

---

Read More

• LeetCode 解題紀錄目錄