字符串无序匹配

给定长度为 m 的字符串 aim，以及一个长度为 n 的字符串 str 问能否在 str 中找到一个长度为 m 的连续子串，使得这个子串刚好由 aim 的 m 个字符组成，顺序无所谓返回任意满足条件的一个子串的起始位置，未找到返回-1。

思路：

找到一个串和aim排序对比

public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            String aim = input.next();
            String str = input.next();
            int m = aim.length();
            int i = 0;
            int j = m - 1;
            char[] charAim = aim.toCharArray();
            Arrays.sort(charAim);
            int flag = 0;
            while (j != m) {
                char[] sub = str.substring(i, j + 1).toCharArray();
                Arrays.sort(sub);
                flag = 0;
                for (int k = 0; k < sub.length; k++) {
                    if (sub[k] != charAim[k]) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 1) {
                    i++;
                    j++;
                    continue;
                } else {
                    System.out.println("true");
                    break;
                }
            }
            if (flag == 1) System.out.println("false");
        }
    }

面试上写这个暴力算法没有分 O(n^3*logN)

优化O(N*M):

public boolean isTY(char[] str, int L, char[] aim) {
        // 0-255 统计数组
        // 'a' 97
        // count[97] ++;
        int[] count = new int[256];
        for (int i = 0; i < aim.length; i++) {
            count[aim[i]]++;
        }
        //count 中含有0-255
        for (int i = 0; i < str.length; i++) {
            if (count[str[i]] == 0) {
                return false;
            }
            count[str[i]]--;
        }
        return true;
    }

    public int containExactly2(String a, String b) {
        if (a == null || b == null || a.length() < b.length()) {
            return -1;
        }
        char[] str = a.toCharArray();
        char[] aim = b.toCharArray();
        for (int L = 0; L <= str.length - aim.length; L++) {
            if (isTY(str, L, aim)) {
                return L;
            }
        }
        return -1;
    }

一共有N-M个要判断匹配的串，要遍历M个长度

最后优化:O(n)

先把目标字符串做成一个字典表。

出现了的字符做成一个计数字典

没有出现的就认为是0

遍历输入字符串的时候

让滑动窗口内的计数减减，多的可以记成负数

每次从窗口右边进来的我都减

从窗口左边画出的我都加一

最终遍历完看无效的负数点有没有来判断有没有同源异构

public int containExactly(String a, String b) {
        if (a == null || b == null || a.length() < b.length()) {
            return -1;
        }
        char[] str = a.toCharArray();
        char[] aim = b.toCharArray();
        int[] count = new int[256];
        for (int i = 0; i < aim.length; i++) {
            count[aim[i]]++;
        }
        int M = aim.length;
        int inValidTimes = 0;
        int R = 0;
        // 先让窗口用于M个字符
        for (; R < M; R++) {
            if (count[str[R]]-- <= 0) {
                inValidTimes++;
            }
        }
        // 如果第一个是同源异构词
        if (inValidTimes == 0) {
            return R - M;
        }
        // 窗口滑动
        for (; R < str.length; R++) {
            if (inValidTimes == 0) {
                return R - M;
            }
            // 0[0..M-1]M
            // [1..M]
            // [2...M+1]
            if (count[str[R]]-- <= 0) {
                inValidTimes++;
            }
            if (count[str[R - M]]++ < 0) {
                inValidTimes--;
            }
        }
        return inValidTimes == 0 ? R - M : -1;
    }