力扣 java 串联所有单词的子串 题解及思路

• 力扣 30. 串联所有单词的子串
• • 描述
  • • 示例1
    • 示例2
    • 示例3
  • 题解
  • • 方法一
    • 代码实现

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

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 “barfoo” 和 “foobar” 。
输出的顺序不重要, [9,0] 也是有效答案。

输入：s = “wordgoodgoodgoodbestword”, words = [“word”,“good”,“best”,“word”]
输出：[]

输入：s = “barfoofoobarthefoobarman”, words = [“bar”,“foo”,“the”]
输出：[6,9,12]

执行用时：10 ms, 在所有 Java 提交中击败了88.50%的用户
内存消耗：41.8 MB, 在所有 Java 提交中击败了90.24%的用户

思路

将字符串s转化为在words中出现的位置下标数组，在下标数组中寻找words下标

如：

s = “barfoothefoobarman” 转化为下标数组：
cut_state = [1,-1,-1,0,-1,-1,-1,-1,-1,1,-1,-1,0,-1,-1,-1,-1]
ps：字符串”bar“在words的位置下标是1，“arf”在words不存在，保存为-1，类推

具体实现思路

先将words数组及其下标存入HashMap中，方便后续读取

使用一个数组words_state记录words字符串数组的状态

由于words数组里的字符串等长，可以使用滑动的方式截取字符串，定义一个数组cut_state保存滑动截取的字符串状态，在HashMap中查找截取到的字符串，找到则在cut_state状态数组保存HashMap中的words对应的字符串下标

遍历状态数组，words_state数组为全部找到时则完全匹配

class Solution {
    public List findSubstring(String s, String[] words) {
        List result = new ArrayList<>();
        int words_len = words.length;
        if(words_len == 0){
            return result;
        }
        int word_len = words[0].length();
        // words状态数组
        int[] words_state = new int[words_len];
        // 滑动截取的字符串状态数组
        int[] cut_state = new int[s.length()];
        
        Map map = new HashMap<>(words_len);
        for(int i=0;i 0){
                sum_state -= 1;
                words_state[val] -= 1;
                bs += 1;
                // 长度超出，结束
                if(bs * word_len + i >= s.length()){
                    if(sum_state == 0){
                        result.add(i);
                    }
                    return result;
                }
                val = cut_state[bs * word_len + i];
                // words_state数组全部找到
                if(sum_state == 0){
                    result.add(i);
                    break;
                }
            }
            // 回溯
            while(--bs >= 0){
                val  = cut_state[bs * word_len + i];
                sum_state += 1;
                words_state[val] += 1;
            }
        }
        return result;
    }
}