【leetcode】字符串的变位词

0、 相关知识

• String contains底层实现原理
  底层做的是最笨的字符串包含算法，就是逐个字符比较，先找第一个相等字符，然后从该字符依次遍历比较，如果未比较成功，则找第二个相等字符，以此类推。
• ArrayList底层实现原理
  for循环遍历集合，逐个比较元素即可，注意空值，如果传入的是对象，需要对象重写equals方法，否则默认调用object的equals
• String常见方法
  indexof contains substring toCharArray charAt
• string stringbuidler stringbuffer 链接
• 相似题目：
• 【leetcode单词长度的最大乘积】
  通过计数数组，判断两个字符串是否有相同字符，当然也可用位运算
• 滑动窗口集合

一、 题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。
换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
1
2
3

二、代码思路

使用滑动窗口的思想：

1. 将整体的 s2 拆成一个个滑动窗口的大小为s1.length的字串。
2. 字串和 s1 全排列的比较如下： 我们可以使用 count数组 统计字符串中每个字符出现的数量。
3. 只要 s1子串 和 s2 字串字符数量一致，也可以说 count 数组一致，那么代表 s1 的全排列可以成为 s2 的子串

三、代码题解

package leetcode;

import java.util.Arrays;

/*
 * @author lzy
 * @version 1.0
 * */
public class SolutionCheckInclusion {
    public static void main(String[] args) {
        String s1 = "ccc";
        String s2 = "cbac";
        System.out.println(checkInclusion(s1,s2));
    }

    public static boolean checkInclusion(String s1, String s2) {
        //使用滑动窗口的思想：
        //1. 将整体的 s2 拆成一个个滑动窗口的大小为s1.length的字串。
        //2. 字串和 s1 全排列的比较如下： 我们可以使用 count数组 统计字符串中每个字符出现的数量。
        //3. 只要 s1子串 和 s2 字串字符数量一致，也可以说 count 数组一致，那么代表 s1 的全排列可以成为 s2 的子串
        int l = 0;
        int r = s1.length() - 1;
        int m = r + 1;
        int n = s2.length();
        //如果 s2 长度小于 s1 长度
        if (n < m) {
            return false;
        }
        //注意：此处不能用位运算，因为我们使用 count 数组来存放每个字符的数量，每个字符的数量可能大于 1
        //如果用二进制位存放字符数量不妥
        //使用滑动窗口来做
        int s2Count[] = new int[26];
        int s1Count[] = new int[26];
        for (int i = 0; i < m; i++) {
            //初始化 s1 的 count数组
            //初始化 s2 字串的count数组
            s1Count[s1.charAt(i) - 'a']++;
            s2Count[s2.charAt(i) - 'a']++;
        }
        if (Arrays.equals(s1Count, s2Count)) return true;
        //固定大小的滑动窗口开始滑动，l++ r++ 一起向右滑动
        while (r < s2.length() - 1) {
            s2Count[s2.charAt(++r) - 'a']++;
            s2Count[s2.charAt(l--) - 'a']--;
            if (Arrays.equals(s1Count, s2Count)) return true;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50