Soyo

May Leetcode Challenge - Day 18

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].

Solution

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        var table = Array(repeating: 0, count: 26)
        var indexes = s2.map { $0.index }
        
        for c in s1 {
            table[c.index] += 1
        }
        
        for i in 0..<indexes.count {
            table[indexes[i]] -= 1
            if i > (s1.count - 1) {
                table[indexes[i - s1.count]] += 1
            }
            if table.hasZeroesOnly  { return true }
        }
        
        return false
    }
}

extension Array where Element == Int {
    var hasZeroesOnly : Bool {
        for val in self {
            if val != 0 { return false }
        }
        return true
    }
}

extension Character {
    var index : Int {
        return Int(self.unicodeScalars.first!.value) - Int(Unicode.Scalar("a").value)
    }
}

Comments