[LeetCode][Kotlin] 567. Permutation in String

567. Permutation in String

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.

두 개의 문자열 s1과 s2가 주어졌을 때, s2에 s1의 순열 이 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 

즉, s1의 순열 중 하나가 s2의 하위 문자열이면 true를 반환합니다.

순열은 문자열의 모든 문자를 재배열하는 것입니다.

 

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

---

코드 1

class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        if (s1.length > s2.length) return false

        val hm1 = HashMap<Char, Int>()
        s1.forEach { hm1[it] = hm1.getOrDefault(it, 0) + 1 }

        val hm2 = HashMap<Char, Int>()
        for (i in s1.indices) {
            hm2[s2[i]] = hm2.getOrDefault(s2[i], 0) + 1
        }
        if (hm1 == hm2) return true

        for (i in s1.length until s2.length) {
            hm2[s2[i - s1.length]] = hm2[s2[i - s1.length]]!! - 1
            if (hm2[s2[i - s1.length]]!! == 0) {
                hm2.remove(s2[i - s1.length])
            }

            hm2[s2[i]] = hm2.getOrDefault(s2[i], 0) + 1
            if (hm1 == hm2) return true
        }

        return false
    }
}

 

코드 2

class Solution {
    fun checkInclusion(s1: String, s2: String): Boolean {
        if (s1.length > s2.length) return false

        val s1Count = IntArray(26)
        val s2Count = IntArray(26)
        for (i in s1.indices) {
            s1Count[s1[i] - 'a'] += 1
            s2Count[s2[i] - 'a'] += 1
        }

        var matches = 0
        for (i in 0..25) {
            matches += if (s1Count[i] == s2Count[i]) 1 else 0
        }

        var l = 0
        for (r in s1.length until s2.length) {
            if (matches == 26) return true

            var index = s2[l] - 'a'
            s2Count[index] -= 1
            if (s1Count[index] == s2Count[index]) {
                matches += 1
            } else if (s1Count[index] == s2Count[index] + 1) {
                matches -= 1
            }

            index = s2[r] - 'a'
            s2Count[index] += 1
            if (s1Count[index] == s2Count[index]) {
                matches += 1
            } else if (s1Count[index] == s2Count[index] - 1) {
                matches -= 1
            }

            l++
        }

        return matches == 26
    }
}