leetcode / anagram in string - some permutation of s1 string is a substring of s2

代码

package com.xcrj;

import java.util.*;

/** * 字符串中的变位词 * s1A certain permutation of the string iss2的子串 * 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的某个变位词. * 换句话说,第一个字符串的排列之一是第二个字符串的 子串 . */
public class Solution14 {
    

    /** * 超过时间限制 * <p> * Incremental brute force method to obtain permutations * 排列kmp算法在s2中 */
    public boolean checkInclusion1(String s1, String s2) {
    
        Set<String> result = fullPermutation(s1);
        for (String str : result) {
    
            if (-1 != kmp(s2, str)) return true;
        }
        return false;
    }

    /** * 增量蛮力法：很耗时 * i=1 set<List1>: 1 * i=2 set<List1*2>: 21 | 12 * i=3 set<List2*3>: 321 231 213 | 312 132 123 * * @param s1 * @return s1数组的全排列 */
    private Set<String> fullPermutation(String s1) {
    
        Set<String> result = new HashSet<>(6);
        Set<List<Integer>> resultIdx = new HashSet<>(6);
        // 元素个数
        int n = s1.length();
        // 初始化 加入1
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        resultIdx.add(list1);
        // 循环加入2 3 ... n等
        for (int i = 2; i <= n; i++) {
    
            Set<List<Integer>> tempResultIdx = new HashSet<>(6);
            // 操作resultIdx中的每个list
            for (List<Integer> list : resultIdx) {
    
                for (int j = 0; j < i; j++) {
    
                    List<Integer> tempList = new ArrayList<>(list.size());
                    // 拷贝list到tempList
                    tempList.addAll(list);
                    // for each permutationlistincrease under different subscriptsi
                    tempList.add(j, i);
                    tempResultIdx.add(tempList);
                }
            }
            // 清空原resultIdx,tempResultIdx copy resultIdx
            resultIdx.clear();
            for (List<Integer> temp : tempResultIdx) {
    
                List<Integer> one = new ArrayList<>(temp.size());
                one.addAll(temp);
                resultIdx.add(one);
            }
        }
        // 根据索引获取元素
        for (List<Integer> list : resultIdx) {
    
            char[] chars = new char[s1.length()];
            for (int i = 0; i < list.size(); i++) {
    
                int idx = list.get(i);
                chars[i] = s1.charAt(idx - 1);
            }
            result.add(new String(chars));
        }

        return result;
    }

    /** * 部分匹配表：！！！Number of matches for prefix and suffix characters * 1characters for the partial match value of the string,2characters for the partial match value of the string,...,ncharacter as a partial match value for a string Form a partial match table * i从第2个字符到第n个字符,j从第1个字符到第n-1个字符 * 1characters as part of the string match value0 * * @param pattern 模式串 待匹配串 s1的某个排列 * @return 部分匹配表 */
    private int[] partialMatchingTable(String pattern) {
    
        int[] next = new int[pattern.length()];
        // 1characters as part of the string match value0
        next[0] = 0;
        // i从第2个字符到第n个字符,j从第1个字符到第n-1个字符
        for (int i = 1, j = 0; i < pattern.length(); i++) {
    
            // Prefix and suffix characters do not match,进行部分匹配,回到上1The location of the subpart match
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
    
                j = next[j - 1];
            }
            // Prefix and suffix characters match,i和jMove backward and compare one character
            if (pattern.charAt(i) == pattern.charAt(j)) {
    
                j++;
            }
            // 0~i的子串的部分匹配值=j
            next[i] = j;
        }

        return next;
    }

    /** * kmp算法 模式匹配算法 * If you can't match all of them, select Partial Match Iridium to reduce the distance of the subscript fallback * How much to back off is determined by the partial match table * Partial match table by  字符串的 最长前缀字符串=最长后缀字符串中 的字符数量 * * @param match 匹配串 s2 * @param pattern 模式串 s1的某个排列 * @ruturn The first occurrence of the pattern string in the matched string */
    public int kmp(String match, String pattern) {
    
        int[] next = partialMatchingTable(pattern);
        // i匹配串下标,j模式串下标
        for (int i = 0, j = 0; i < match.length(); i++) {
    
            // i和jThe pointed character does not match,进行部分匹配,回到上1The location of the subpart match
            while (j > 0 && match.charAt(i) != pattern.charAt(j)) {
    
                j = next[j - 1];
            }
            // i和jThe pointed character matches,i和j都后移 比较下1个字符
            if (match.charAt(i) == pattern.charAt(j)) {
    
                j++;
            }
            // 全部匹配,Returns the starting position of the pattern string within the matched string
            if (j == pattern.length()) {
    
                return i - j + 1;
            }
        }

        return -1;
    }

    /** * 滑动窗口 * The topic doesn't cares1中的字符在s2中的顺序,worth carings2The character sum in the neutron sequences1Is the number of occurrences of the characters equal * 转化为判断 Whether the hash table that counts the occurrences of a character is equal * 数组散列表,散列函数 idx=c-26 * * @param s1 短字符串 * @param s2 长字符串 */
    public boolean checkInclusion2(String s1, String s2) {
    
        int m = s1.length();
        int n = s2.length();
        // s1比s2更长
        if (m > n) {
    
            return false;
        }

        // 散列表, 26个字母
        int[] cnts1 = new int[26];
        int[] cnts2 = new int[26];
        // 统计0~s1.length()-1长度s1中字符出现的次数,s2中字符出现的次数
        for (int i = 0; i < s1.length(); i++) {
    
            ++cnts1[s1.charAt(i) - 'a'];
            ++cnts2[s2.charAt(i) - 'a'];
        }
        // s1A sequence of some order is s2的前缀
        // 比较1Array hash table
        if (Arrays.equals(cnts1, cnts2)) {
    
            return true;
        }
        // The length of the fixed sliding window is m,因为s1的长度为m
        for (int i = m; i < n; i++) {
    
            // 窗口往右滑动,Enter a character on the right side of the window
            ++cnts2[s2.charAt(i) - 'a'];
            // 窗口往右滑动,A character goes out on the left side of the window
            --cnts2[s2.charAt(i - m) - 'a'];
            if (Arrays.equals(cnts1, cnts2)) {
    
                return true;
            }
        }

        return false;
    }

    /** * 将原来的cnts1和cnts2合并为1个cnts,并使用diff统计cnts[i]!=0的元素个数 */
    public boolean checkInclusion3(String s1, String s2) {
    
        int m = s1.length();
        int n = s2.length();
        if (m > n) {
    
            return false;
        }
        // 散列表, 26个字母
        int[] cnts = new int[26];
        // 统计0~s1.length()-1长度s1中字符出现的次数,s2中字符出现的次数
        for (int i = 0; i < s1.length(); i++) {
    
            // A new element is entered in the window s1减法
            --cnts[s1.charAt(i) - 'a'];
            // A new element is entered in the window s2加法
            ++cnts[s2.charAt(i) - 'a'];
        }
        // 记录差异
        int diff = 0;
        for (int c : cnts) {
    
            if (c != 0) {
    
                diff++;
            }
        }
        // s1A sequence of some order is s2的前缀
        if (0 == diff) return true;
        // 滑动窗口
        /** * diff记录差异： * - diff+1：cnts[x]!=0 cnts[y]!=0 * - diff-1：cnts[x]=0 cnts[y]=0 * New in and out characters are the same： * - ++cnts[x]再--cnts[x],There is no change to look directly at the next character * The newly entered and exited characters are the same and different： * - 进入x,一定++cnts[x].++cnts[x]之前,若cnts[x]=0,则diff+1;++cnts[x]之后,若cnts[x]=0,则diff-1. * - 退出y,一定--cnts[y].--cnts[y]之前,若cnts[y]=0,则diff+1; --cnts[y]之后,若cnts[y]=0, 则diff-1. */
        for (int i = m; i < n; ++i) {
    
            // Incoming character hash value
            int x = s2.charAt(i) - 'a';
            // The character hash value that goes out
            int y = s2.charAt(i - m) - 'a';
            // New in and out characters are the same：++cnts[x]再--cnts[x],There is no change to look directly at the next character
            if (x == y) {
    
                continue;
            }
            // 修改cnts[]之前,若cnts1[x]=cnts2[x],will increase the difference diff+1
            if (cnts[x] == 0) {
    
                ++diff;
            }
            // A new element is entered in the window s2加法
            ++cnts[x];
            // 修改cnts[]之后,若cnts1[x]=cnts2[x],will reduce the difference diff-1
            if (cnts[x] == 0) {
    
                --diff;
            }
            if (cnts[y] == 0) {
    
                ++diff;
            }
            --cnts[y];
            if (cnts[y] == 0) {
    
                --diff;
            }
            if (diff == 0) {
    
                return true;
            }
        }
        return false;
    }

    /*** * 在cnts[]When the element value is not positive,s2There is no length for m的连续子数组 * 连续子数组,使用双指针 */
    public boolean checkInclusion4(String s1, String s2) {
    
        int m = s1.length();
        int n = s2.length();
        if (m > n) {
    
            return false;
        }
        // 散列表, 26个字母
        int[] cnts = new int[26];
        // 统计0~s1.length()-1长度s1中字符出现的次数
        // ！！！cnts[]元素之和为-m
        for (int i = 0; i < s1.length(); i++) {
    
            // A new element is entered in the window s1减法
            --cnts[s1.charAt(i) - 'a'];
        }
        // 在cnts[]When the element value is not positive,s2There is no length for m的子数组
        // ！！！right-left+1,each increase in length1,cnts[]The sum of the elements increases1
        for (int left = 0, right = 0; right < n; right++) {
    
            // 右移++
            ++cnts[s2.charAt(right) - 'a'];
            // 保证cnts[]Element value is not positive,A positive left shift is encounteredleft
            while (cnts[s2.charAt(right) - 'a'] > 0) {
    
                // 左移--
                --cnts[s2.charAt(left) - 'a'];
                left++;
            }
            // s2There is no length for m的子数组
            // !!! 当right - left + 1 长度等于 m时,cnts[]元素之和为0
            if (right - left + 1 == m) {
    
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
    
        Solution14 solution14 = new Solution14();
        System.out.println(solution14.checkInclusion3("pro", "properties"));
    }
}