567. Permutation in String

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

• CTCI 1.2 Check Permutation

Python

Slide Window

from collections import Counter


class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        length_diff = len(s2) - len(s1)

        if length_diff < 0:
            return False

        s1_count = Counter(s1)

        for i in range(0, length_diff+1):
            for char, count in Counter(s2[i:i+len(s1)]).items():
                if s1_count.get(char) != count:
                    break
            else:
                # If inner loop not be broken, there is the answer
                return True

        return False

Rust

Slide Window

use std::collections::HashMap;


impl Solution {
    fn gen_map(s: &String) -> String {
        let mut mapper = [0; 26];
        for i in s.as_bytes().iter() {
            mapper[(i-b'a') as usize] += 1;
        }
        mapper.iter().map(|&count| count.to_string()).collect()
    }

    pub fn check_inclusion(s1: String, s2: String) -> bool {
        if s1.len() > s2.len() {
            return false;
        }

        let mapper = Solution::gen_map(&s1);
        let len_diff = s2.len() - s1.len();

        for i in 0..len_diff+1 {
            let sub_s2 = &s2[i..i+s1.len()].to_string();
            let sub_s2_map = Solution::gen_map(&sub_s2);

            if sub_s2_map == mapper {
                return true;
            }
        }

        false
    }
}