leetcode-567 字符串的排列
题目描述:
给定两个字符串? s1? 和? s2, 写一个函数来判断? s2? 是否包含? s1? 的排列.
换句话说, 第一个字符串的排列之一是第二个字符串的子串.
示例 1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
?
示例 2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
?
注意:
输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间
解法一: sliding Windows(滑动窗口) 法来做
每次 s2 中截取和 s1 等长的字符串, 与 s1 进行比较, 利用数组来统计 a-z 的数量, 辅助比较
java 实现如下:
- class Solution {
- public boolean checkInclusion(String s1, String s2) {
- //s1 小字符串 s2 大字符串 s1>= s2
- if(s1.length()> s2.length()) return false;
- int[] count = new int[26];
- for(int i = 0; i <s1.length();i++){
- //charat (i) 返回字符串 s1 的第 i 个字符. 假设此字符串只包含小写字母 (即将字符 "a" 映射到索引 0,
- // 将字符 "b" 映射到索引 1, 以此类推 (将 "z" 映射到索引 25).
- count[s1.charAt(i) - 'a'] ++;
- count[s2.charAt(i) - 'a'] --;
- }
- if(helper(count)){
- return true;
- }
- for(int i = s1.length(); i < s2.length(); i++){
- count[s2.charAt(i) - 'a'] --;
- count[s2.charAt(i - s1.length()) - 'a'] ++;
- if(helper(count)){
- return true;
- }
- }
- return false;
- }
- // 数组为空返回 true
- public boolean helper(int[] count){
- for(int num: count){
- if(num != 0){
- return false;
- }
- }
- return true;
- }
- }
c++ 实现如下:
- class Solution {
- public:
- bool checkInclusion(string s1, string s2) {
- int n1 = s1.size(), n2 = s2.size(),left = 0;
- vector<int> m(128);
- for(char c: s1) ++m[c];
- for(int right = 0; right < n2; ++right){
- if(--m[s2[right]] < 0){
- while(++m[s2[left++]] != 0){}
- }else if(right - left + 1 == n1) return true;
- }
- return n1 == 0;
- }
- };
来源: http://www.bubuko.com/infodetail-3044912.html