2018-10-30 20:53:15 +0000   |     algorithm leetcode string   |   Viewed times   |    

题目

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

Note:

窗口法

核心问题在于怎么记录Permutation的特征信息?最简便的方法就是用一个int[26]统计每个字母的出现的频率。因为无论abb,bab还是bba,本质就是1个a加上2个b

先统计出s1的字母频率,然后在s2上开一个和s1一样大小的窗口,统计窗口内字母的频率,

ab:
 a b
[1,1,0,0,0,0,0,0,0,0,0...0]

         e       i
[0,0,0,0,1,0,0,0,1,0,0...0]
|-|
eidbaooo

        d         i
 [0,0,0,1,0,0,0,0,1,0,0...0]
 |-|
eidbaooo

...
...

    a b
   [1,1,0,0,0,0,0,0,0,0,0...0]
   |-|
eidbaooo

代码

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        char[] c1 = s1.toCharArray();
        int[] count1 = new int[26];
        for (char c : c1) count1[c - 'a']++;
        char[] c2 = s2.toCharArray();
        int[] count2 = new int[26];
        for (int i = 0; i < c1.length; i++) count2[c2[i] - 'a']++;
        for (int lo = 0, hi = c1.length; hi < c2.length; lo++, hi++) {
            if (Arrays.equals(count1, count2)) return true;
            count2[c2[lo] - 'a']--;
            count2[c2[hi] - 'a']++;
        }
        if (Arrays.equals(count1, count2)) return true;
        return false;
    }
}

结果

permutation-in-string-1