LeetCode 567. Permutation in String

题目

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

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


Note:

The input strings only contain lower case letters.  
The length of both given strings is in range [1, 10,000].  

思路

看到题目的时候有想到用一个hashtable 来存每个char的count, 然后iterate s2, 当存在的时候就减1, 顺着这个思路先写了第一个版本

func checkInclusion(_ s1: String, _ s2: String) -> Bool {  
        var dict = [Character: Int]()

        for char in s1 {
            if var current = dict[char] {
                current += 1
                dict[char] = current
            } else {
                dict[char] = 1
            }
        }

        var copy = dict
        for (index, _) in s2.enumerated() {
            let currentStringIndex = s2.index(s2.startIndex, offsetBy: index)
            let sub = s2[currentStringIndex..<s2.endIndex]
            let result = helper(s: String(sub), dict: &copy)
            if result {
                return true
            } else {
                copy = dict
            }
        }

        return false
    }

    func helper(s: String, dict: inout [Character: Int]) -> Bool {
        for char in s {
            if var current = dict[char] {
                if current == 1 {
                    dict.removeValue(forKey: char)

                    if dict.isEmpty {
                        return true
                    }
                } else {
                    current -= 1
                    dict[char] = current
                }
            } else {
                return false
            }
        }

        return false
    }

可行,但是提交的时候timeout, 说明不够优化。于是看了一下discussion和一个Youtube, 原来tricky之处在于可以用sliding window的方式来解决, 于是有了下面的版本,这次就可以过了

func checkInclusion(_ s1: String, _ s2: String) -> Bool {  
        var s1Map = Array(repeating: 0, count: 26)
        var s2Map = s1Map
        let indexA = Character("a").asciiValue!

        for char in s1 {
            let charIndex = Int(char.asciiValue! - indexA)
            s1Map[charIndex] += 1
        }

        var charIndexes = [Int]()
        for char in s2 {
            let charIndex = Int(char.asciiValue! - indexA)
            charIndexes.append(charIndex)
        }

        let window = s1.count

        for (index, charIndex) in charIndexes.enumerated() {
            let left = index - window

            s2Map[charIndex] += 1
            if left >= 0 {
                let leftCharIndex = charIndexes[left]
                s2Map[leftCharIndex] -= 1
            }

            if s1Map == s2Map {
                return true
            }
        }

        return false
    }

chenbo

编程爱好者

Singapore