567. Permutation in String
Problem statement:
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
Solution one: DFS permutation and string match.
This is the third question of leetcode weekly contest 30. I find an approach to solve this problem, it does not accept since of the TLE error.
Like 46. Permutations, I find all permutations and check the string if current permutation exists in the s2. It costs times.
To find all permutations, it costs O(n ^ n).
Since I did not save the code, and a long time after the computation, just brief describe the idea.
Solution two: sliding window.
The problem asks the permutation, it contains two key information: (1) the order does not matter. (2) the letters are consecutive.
Basic above two characteristics, we can use a sliding window to solve this problem, which is different with 424. Longest Repeating Character Replacementand 594. Longest Harmonious Subsequence, the size of sliding window is fixed(the length of s1).
Suppose the length of s1 is k, s2 is n. The basic steps include:
- Initialize the sliding window with first k elements. We should check if letters in current sliding window equal to s1.
- Each time when we moved forward while erasing the element out of the sliding window.
Time complexity is O(k * n).
class Solution {
public:
bool checkInclusion(string s1, string s2) {
if(s1.size() > s2.size()){
return false;
}
int s1_len = s1.size();
int s2_len = s2.size();
vector<int> s1_cnt(, );
vector<int> s2_cnt(, );
for(int ix = ; ix < s1_len; ix++){
s1_cnt[s1.at(ix) - 'a']++;
}
for(int ix = ; ix < s2_len; ix++){
s2_cnt[s2.at(ix) - 'a']++;
if(ix >= s1_len){
s2_cnt[s2.at(ix - s1_len) - 'a']--;
}
if(s1_cnt == s2_cnt){
return true;
}
}
return false;
}
};
最新文章
- 参数*args和**args区别
- Android程序设计-RecyclerView的使用
- 【HDU 5105】Math Problem
- BZOJ 3140 消毒(最小顶点覆盖)
- Forward Proxy & Reverse Proxy | 正向代理 和 反向代理
- SQL Server 阻塞排除的 2 方法
- 如何在Java中避免equals方法的隐藏陷阱
- C++并发高级接口：std::async和std::future
- 查看Linux下系统资源占用常用命令(top、free、uptime)
- Linux负载查询定位工具
- MySql数据库学习笔记（1）
- hdu5421Victor and String 两端加点的pam
- SHOW Syntax
- 附录A Spring Boot应用启动器
- 关于 redis、memcache、mongoDB 的对比 转
- XAMPP下apache部署网站，多个虚拟机（空间）配置
- SICP读书笔记 3.1
- [Luogu 3952] NOIP2017 时间复杂度
- linux下设置 git ssh 代理
- 记一次生产环境axis2服务特别慢的问题。