Algorithem_PermutationInString
原创Algorithem_PermutationInString
原创
莫空9081
发布于 2022-04-24 11:27:48
发布于 2022-04-24 11:27:48
Algorithem_PermutationInString
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.
<!--more-->
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解法
首先理解 Permutation的意思，题目需要的是 s2包含 s1中字符串的任意一种排列，就返回 true，否则返回 false。即比如 s1 = 'abc'，那么 s1的排列有'abc'、'aca'、'bac'、'bca'、'cba'、'cab' 6中，当字符个数越多排列的种类也越多，所以想要通过枚举 s1的排列，然后判断s2中是否包含这些排列的方法，太麻烦。
那么要怎么解呢？假如s2包含 s1的排列，那么肯定是 s2中 s1长度的 subString 和 s1的某种排列一样，所以可以通过 SlidingWindow算法
- Window 的长度是 s1的长度，从0开始，每次取 window 长度的 substring
- 如何比较s2的 substring 和 s1的某种排列是否相等呢？不论s1的排列是什么样，字符出现的次数是固定的，比如 s1=abc，其中一定是a出现一次、b 出现一次、c 出现一次。所以用字典存储，key是Character，value 是 出现的次数，先把 s1的存起来，然后把 s2的同样长度的 substring 也生成一个同样类型的字典，然后比较两个字典的 key 和 value 是否一致，从而就能比较
代码如下：
class Solution {
func checkInclusion(_ s1: String, _ s2: String) -> Bool {
if s1.length > s2.length || s2.length == 0 {
return false
}
if s1.length == 0 {
return true
}
let s1CharList = Array(s1)
let s2CharList = Array(s2)
let s1Count = s1CharList.count
let s2Count = s2CharList.count
let map1: [Character: Int] = generateMap(s1CharList)
for i in 0..<s2Count-s1Count+1 {
let item = s2CharList[i]
if map1.keys.contains(item) {
let map2: [Character: Int] = generateMap(Array(s2CharList[i..<i+s1Count]))
let findEqual = map1 == map2
if findEqual {
return true
}
}
}
return false
}
func generateMap(_ list: [Character]) -> [Character: Int] {
var map1: [Character: Int] = [:]
for t in list {
if let tcount = map1[t] {
map1[t] = tcount + 1
}
else {
map1[t] = 1
}
}
return map1
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录