LeetCode30. 串联所有单词的子串

LeetCode30. 串联所有单词的子串

题目描述

 /**
     * 
     * 给定一个字符串 s 和一些 长度相同 的单词 words 。
     * 找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
     * <p>
     * 注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，
     * 但不需要考虑 words 中单词串联的顺序
     * 
     */

思路分析

1. 使用滑动窗体的思想
2. 窗体的大小为字符串数字的长度 * 每个字符串字符的长度
3. 从零开始遍历字符串s，每次取窗体大小个字符，因为字符串数组中字符串的长度是固定的，截取指定长度的字符串，和字符串数组中的字符串组成的长串相比
4. 判断一个长串中是否包含子字符串的任意排列组合，可以考虑使用比较哈希表的方法
5. 哈希表的键存储子字符串，值存储字符串出现的次数
6. 如果两个哈希表相同，则保存索引返回继续下一次循环

源码及详解

public List<Integer> findSubstring(String s, String[] words) {
        //定义集合保存索引
        ArrayList<Integer> list = new ArrayList<>();
        //字符串数组的长度
        int strsLen = words.length;
        //字符串数组中每个字符串的长度
        int wordLen = words[0].length();
        //则滑动窗口的长度为 strsLen * wordLen
        int windowLen = strsLen * wordLen;
        //将字符串数组中字符串存储到哈希表中，key存储字符串，value存储字符串出现的次数
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            //如果键存在，返回键所映射的值，如果键不存在返回默认值
            Integer value = map.getOrDefault(word, 0);
            map.put(word, value + 1);
        }
        //然后把一个窗口中的字符串拆分成子串存储到哈希表中，如果哈希表相同，则匹配
        //字符串s的长度
        int strLen = s.length();
        for (int i = 0; i < strLen - windowLen + 1; i ++) {
            //拿到每一个窗口,并将窗口中的字符串切割为成为为wordLen的子串
            String window = s.substring(i, windowLen + i);
            String[] subStr = new String[strsLen];
            int k = 0;
            for (int j = 0; j < windowLen - wordLen + 1; j += wordLen) {
                subStr[k] = window.substring(j,j + wordLen);
                k++;
            }

            //存入哈希表中
            HashMap<String, Integer> tmpMap = new HashMap<>();
            for (String s1 : subStr) {
                Integer value = tmpMap.getOrDefault(s1, 0);
                tmpMap.put(s1, value + 1);
            }
            //判断两个哈希表是否相等
            boolean flag = true;
            //先判断键是否相等，采用你中是否有我，我中是否有你的思路
            Set<String> keySet = map.keySet();
            Set<String> tmpSet = tmpMap.keySet();
            for (String key : keySet) {
                if (!tmpSet.contains(key)) {
                    flag = false;
                    break;
                }
            }
            if (!flag){
                continue;
            }
            for (String key : tmpSet) {
                if (!keySet.contains(key)) {
                    flag = false;
                    break;
                }
            }
            if (!flag){
                continue;
            }
            //再由键比较值
            for (String key : keySet) {
                int integer1 = map.get(key);
                int integer2 = tmpMap.get(key);
                if (integer1 != integer2) {
                    flag = false;
                }
            }
            if (!flag){
                continue;
            }
            //过关斩将法，如果前变条件都成立，则此子串满足，添加索引
            list.add(i);
        }
        return list;
    }

LeetCode30. 串联所有单词的子串

原文：https://www.cnblogs.com/mx-info/p/14790486.html