【子串查找】在字符串中找出子串第一次出现的位置,所有出现的位置(次数),是否包含子串

子串查找

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

给定两个字符串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个字母放入keyvalue全部为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;
}
    原文作者:iqqcode
    原文地址: https://blog.csdn.net/weixin_43232955/article/details/108895535
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞