LeetCode Permutation in String

· 131 words · 1 minute read
2017年6月
LeetCode

567. Permutation in String

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

方法

该题目意思不仅仅只是逆序，Permutation译为置换，包含各种排列组合，由于字符串只包含小写字母，所以可以先生成大小为26的数组count，将s1中的字母出现的次数存于count。用两个指针i,j遍历s2，当j-i+1 == s1.length() 说明在s2中存在s1的Permutation。count[s2.charAt(j)-'a']-- == 0，while(++count[s2.charAt(i++)-'a'] != 0){}指的是遍历s2，当s2的字母没有出现在s1时，之前减去的数都加回，从新的i的开始再继续遍历。

对于遇到Permutation的问题，常把s1的符号存在数组中，数组大小一般为256或者26,然后再遍历s2，用两个前后指针进行判断。

public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] count = new int[26];
        for(int i = 0; i < s1.length(); i++){
            count[s1.charAt(i)-'a']++;
        }
        for(int i = 0, j = 0; j < s2.length(); j++){
            if(count[s2.charAt(j)-'a']-- == 0){
                while(++count[s2.charAt(i++)-'a'] != 0){
                }
            }else if(j-i+1 == s1.length()){
                return true;
            }
        }
        return false;
    }
}
Share