---

📚题目一：子串第一次出现的位置

给定两个字符串str1和str2，找到str2在str1第一次出现的位置。

str1 = "aefbbcabc"
str2 = "bc"
输出 >>> 4

str1 = "bcbcbc"
str2 = "bc"
输出 >>> 0

👊思考：如果是统计子串所有出现的下标呢？

1. 调用API，String的indexOf方法

【indexOf解决战斗】

public static int indexOfStr_I(String str, String sub) {
	return str.indexOf(sub);
}

2. 截取目标串的长度进行匹配

【思路】

从str1中截取和str2长度一样的字符串，和str2比较，相等即找到，不相等再截取一个新的字符串，直到找到或找不到

public static int findSubString_II(String str1, String str2) {
    int offset = 0;
    String substr = null;
    if ((str1 == null) || (str2 == null) || (str1.length() < str2.length())) {
        return -1;
    } else {
        while (offset <= (str1.length() - str2.length())) {
            //String.copyValueOf(要复制的字符数组, 开始索引, 复制长度)
            substr = String.copyValueOf(str1.toCharArray(), offset, str2.length());
            if (substr.equals(str2)) {
                return offset;
            }
            offset++;
        }
        return -1;
    }
}

🔗Java String copyValueOf方法

3. 滑动窗口

【思路】

在str1中找str2中第一个字符出现的位置，然后再一个字符一个字符的比较str1和str2，如果到str2结束都相等，则找到str2在str1中第一次出现的位置。否则再在str1中找str2的第一字符出现的位置

public static int slideToSubString_III(String str, String sub) {
    int i = 0, j = 0;
    int index = 0;
    while (i < str.length() && j < sub.length()) {
        if (str.charAt(i) == sub.charAt(j)) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
        if (j == sub.length()) {
            return i - j;
        }
    }
    return 0;
}

🎈题目二：子串出现的位置（次数）

测试用例

输入 >>>
源字符串：String str = "www.baidu.com/www.sina.com---www";

目标字符串：String sub = "www";

输出 >>> 3, [0, 14, 29]

1. indexOf方法

使用String类的indexOf方法，每次找到第一次出现的子串后，改变起始寻找位置

lastIndexOf是从后往前找

public static void checkI(String str, String subStr) {
    int index = 0, count = 0;
    List<Integer> list = new ArrayList<>();
    while (index <= str.length()) {
        index = str.indexOf(subStr, index);
        if (index == -1) {
            break;
        }
        list.add(index);
        index += 1;
        count++;
    }
    System.out.println(list);
    System.out.println(count);
}

2. split根据子串分割字符数组，统计子串出现次数

【思路】: 通过str.split(subStr)，将子串放入到字符串数组中，返回数组长度即可

无法记录出现位置

• 使用子串来切割父串，根据结果数组长度获取次数
• 考虑特殊情况–> 子串在末尾，要给截取结果数组长度加1

public static void checkII(String str, String subStr) {
    int count = 0;
    String[] arr = str.split(subStr);
    int len = arr.length;
    if (str.endsWith(subStr)) {
        //如果子串在末尾
        len++;
    }
    count = len - 1;
    System.out.println(count);
}

3. 字符串切割，统计子串出现次数

【思路】: indexOf方法记录子串存现的位置，类比方法一

无法记录出现位置

public static void checkIII(String str, String subStr) {
    // 定义计数器
    int count = 0;
    // 定义变量，保存indexOf查找后的结构
    int index = 0;
    // 开始循环找,条件，indexOf == -1字符串没有了
    // 先用str.indexOf(key)找索引赋值给index，如果index=-1，则说明有字符串
    while ((index = str.indexOf(subStr)) != -1) {
        count++;
        //获取索引，和字符串长度求和，截取字符串
        str = str.substring(index + subStr.length());
    }
    System.out.println(count);
}

4. 正则表达式，统计子串出现次数

public static void checkIV(String str, String subStr) {
    int count = 0;
    Pattern pattern = Pattern.compile(subStr);
    Matcher matcher = pattern.matcher(str);
    while (matcher.find()) {
        count++;
        //group方法返回由以前匹配操作所匹配的输入子序列
        System.out.println("匹配项" + count + "：" + matcher.group());
    }
    System.out.println("匹配个数为" + count);
}

🍳题目三：是否包含子串

最高效的方式，使用contains方法

源串.contains(子串)

• 【方法二】通过 substring() 方法对长字符串a进行截取，然后依次和b字符串进行比较，相同就返回true并且跳出，不相同就移位继续比较

🔗其他方法参考

📌题目四：是否包含子串中的所有字符(无序, 包含即可)

问题：

比较两个字符串A和B，确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母。

• 给出 A = “ABCD” B = “ACD”，返回 true
• 给出 A = “ABCD” B = “AABC”， 返回 false

注意事项：

在 A 中出现的 B 字符串里的字符不需要连续或者有序。

---

【分析】

实质上利用的是哈希表的思想。只有大写字母，一共26个，遍历A的时候，往里面压，遍历B的时候，往外边弹，如果不够弹，则不包含。

1. 计数排序思想

利用下标偏移量，数组元素统计出现次数(计数排序思想)，index[i]小于0则不包含

public static boolean containsCharacterI(String str, String subStr) {
    int[] index = new int[26];
    for (int i = 0; i < str.length(); i++) {
        index[str.charAt(i) - 'A']++;
    }
    for (int i = 0; i < subStr.length(); i++) {
        index[subStr.charAt(i) - 'A']--;
        if (index[subStr.charAt(i) - 'A'] < 0) {
            return false;
        }
    }
    return true;
}

2. HashMap

• 先将26个字母放入key，value全部为0
• 统计源串的字母频率++
• 子串字母--
• 出现 value < 0，则不包含

public static boolean containsCharacterII(String str, String subStr) {
    Map<Character, Integer> map = new HashMap<>();
    // 放入26个大写字母
    for (int i = 0; i < 26; i++) {
        map.put((char) (i + 65), 0);
    }
    // 字符统计
    for (int i = 0; i < str.length(); i++) {
        Character key = str.charAt(i);
        map.put(str.charAt(i), map.get(key) + 1);
    }
    for (int i = 0; i < subStr.length(); i++) {
        Character key = subStr.charAt(i);
        if (map.containsKey(key)) {
            map.put(key, map.get(key) - 1);
        }
        if (map.get(key) < 0) return false;
    }
    return true;
}