[LeetCode] 567. Permutation in String

轉自LeetCode

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.

Solution

可以沿用 76. Minimum Window Substring 的想法

要找 permutation 其實就是要把 s1 的每個字元都用到

所以在這題，只要改一下終止條件就可以

只要找到 subsstring 的長度和 s1 一樣，就可以回傳 true

如果沒找到，就回傳 false

kotlin

	class Solution {
	fun checkInclusion(s1: String, s2: String): Boolean {
	val map = mutableMapOf<Char,Int>()
	for(c in s1) {
	map[c] = map[c]?.let { it + 1 } ?: 1
	}
	var left = 0
	var cnt = 0
	for(right in s2.indices) {
	if(map[s2[right]] != null) {
	map[s2[right]] = map[s2[right]]!! - 1
	if(map[s2[right]]!! >= 0) {
	++cnt
	}
	}
	while(cnt == s1.length) {
	if(right - left + 1 == s1.length) {
	return true
	}
	if(map[s2[left]] != null) {
	map[s2[left]] = map[s2[left]]!! + 1
	if(map[s2[left]]!! > 0) {
	--cnt
	}
	}
	++left
	}
	}
	return false
	}
	}

view raw permutation_in_string.kt hosted with ❤ by GitHub