Welcome to Subscribe On Youtube

567. Permutation in String

Description

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.

Solutions

  • class Solution {
        public boolean checkInclusion(String s1, String s2) {
            int n = s1.length();
            int m = s2.length();
            if (n > m) {
                return false;
            }
            int[] cnt = new int[26];
            for (int i = 0; i < n; ++i) {
                --cnt[s1.charAt(i) - 'a'];
                ++cnt[s2.charAt(i) - 'a'];
            }
            int diff = 0;
            for (int x : cnt) {
                if (x != 0) {
                    ++diff;
                }
            }
            if (diff == 0) {
                return true;
            }
            for (int i = n; i < m; ++i) {
                int a = s2.charAt(i - n) - 'a';
                int b = s2.charAt(i) - 'a';
                if (cnt[b] == 0) {
                    ++diff;
                }
                if (++cnt[b] == 0) {
                    --diff;
                }
                if (cnt[a] == 0) {
                    ++diff;
                }
                if (--cnt[a] == 0) {
                    --diff;
                }
                if (diff == 0) {
                    return true;
                }
            }
            return false;
        }
    }
    
  • class Solution {
    public:
        bool checkInclusion(string s1, string s2) {
            int n = s1.size(), m = s2.size();
            if (n > m) {
                return false;
            }
            vector<int> cnt(26);
            for (int i = 0; i < n; ++i) {
                --cnt[s1[i] - 'a'];
                ++cnt[s2[i] - 'a'];
            }
            int diff = 0;
            for (int x : cnt) {
                if (x) {
                    ++diff;
                }
            }
            if (diff == 0) {
                return true;
            }
            for (int i = n; i < m; ++i) {
                int a = s2[i - n] - 'a';
                int b = s2[i] - 'a';
                if (cnt[b] == 0) {
                    ++diff;
                }
                if (++cnt[b] == 0) {
                    --diff;
                }
                if (cnt[a] == 0) {
                    ++diff;
                }
                if (--cnt[a] == 0) {
                    --diff;
                }
                if (diff == 0) {
                    return true;
                }
            }
            return false;
        }
    };
    
  • class Solution:
        def checkInclusion(self, s1: str, s2: str) -> bool:
            n, m = len(s1), len(s2)
            if n > m:
                return False
            cnt = Counter()
            for a, b in zip(s1, s2):
                cnt[a] -= 1
                cnt[b] += 1
            diff = sum(x != 0 for x in cnt.values())
            if diff == 0:
                return True
            for i in range(n, m):
                a, b = s2[i - n], s2[i]
    
                if cnt[b] == 0:
                    diff += 1
                cnt[b] += 1
                if cnt[b] == 0:
                    diff -= 1
    
                if cnt[a] == 0:
                    diff += 1
                cnt[a] -= 1
                if cnt[a] == 0:
                    diff -= 1
    
                if diff == 0:
                    return True
            return False
    
    
  • func checkInclusion(s1 string, s2 string) bool {
    	n, m := len(s1), len(s2)
    	if n > m {
    		return false
    	}
    	cnt := [26]int{}
    	for i := range s1 {
    		cnt[s1[i]-'a']--
    		cnt[s2[i]-'a']++
    	}
    	diff := 0
    	for _, x := range cnt {
    		if x != 0 {
    			diff++
    		}
    	}
    	if diff == 0 {
    		return true
    	}
    	for i := n; i < m; i++ {
    		a, b := s2[i-n]-'a', s2[i]-'a'
    		if cnt[b] == 0 {
    			diff++
    		}
    		cnt[b]++
    		if cnt[b] == 0 {
    			diff--
    		}
    		if cnt[a] == 0 {
    			diff++
    		}
    		cnt[a]--
    		if cnt[a] == 0 {
    			diff--
    		}
    		if diff == 0 {
    			return true
    		}
    	}
    	return false
    }
    
  • function checkInclusion(s1: string, s2: string): boolean {
        // 滑动窗口方案
        if (s1.length > s2.length) {
            return false;
        }
    
        const n = s1.length;
        const m = s2.length;
    
        const toCode = (s: string) => s.charCodeAt(0) - 97;
        const isMatch = () => {
            for (let i = 0; i < 26; i++) {
                if (arr1[i] !== arr2[i]) {
                    return false;
                }
            }
            return true;
        };
    
        const arr1 = new Array(26).fill(0);
        for (const s of s1) {
            const index = toCode(s);
            arr1[index]++;
        }
    
        const arr2 = new Array(26).fill(0);
        for (let i = 0; i < n; i++) {
            const index = toCode(s2[i]);
            arr2[index]++;
        }
    
        for (let l = 0, r = n; r < m; l++, r++) {
            if (isMatch()) {
                return true;
            }
    
            const i = toCode(s2[l]);
            const j = toCode(s2[r]);
            arr2[i]--;
            arr2[j]++;
        }
        return isMatch();
    }
    
    
  • use std::collections::HashMap;
    
    impl Solution {
        // 测试两个哈希表是否匹配
        fn is_match(m1: &HashMap<char, i32>, m2: &HashMap<char, i32>) -> bool {
            for (k, v) in m1.iter() {
                if m2.get(k).unwrap_or(&0) != v {
                    return false;
                }
            }
            true
        }
        pub fn check_inclusion(s1: String, s2: String) -> bool {
            if s1.len() > s2.len() {
                return false;
            }
            let mut m1 = HashMap::new();
            let mut m2 = HashMap::new();
            // 初始化表 1
            for c in s1.chars() {
                m1.insert(c, m1.get(&c).unwrap_or(&0) + 1);
            }
            let cs: Vec<char> = s2.chars().collect();
            // 初始化窗口
            let mut i = 0;
            while i < s1.len() {
                m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
                i += 1;
            }
            if Self::is_match(&m1, &m2) {
                return true;
            }
            // 持续滑动窗口,直到匹配或超出边界
            let mut j = 0;
            while i < cs.len() {
                m2.insert(cs[j], m2.get(&cs[j]).unwrap_or(&1) - 1);
                m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
                j += 1;
                i += 1;
                if Self::is_match(&m1, &m2) {
                    return true;
                }
            }
            false
        }
    }
    
    

All Problems

All Solutions