参考资料
练习题 icon lost
交流讨论
笔记
img lost

题目

给定一个字符串 s 和一些长度相同的单词 **words。**找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。

示例 1:

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

示例 2:

输入:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出:[]

题解

无官方题解

这道题自己的实现见下面感想部分,感觉方法很蠢,复杂度比较高,就不往题解里贴了——算法太菜了简直不好意思……

感觉遍历s的部分可以动态规划优化一下,有评论区大佬提到了我没听过的方法:ac自动机,不知道是不是就是做这部分动态规划的优化的。

学习的资料:

AC自动机 算法详解(图解)及模板

AC自动机算法详解 (转载)

Trie图(DFA),AC自动机

ac自动机和trie图

感觉这玩意有点厉害,多串形式的kmp啊。AC自动机基本上依赖于字典树Trie的实现,是一种有限状态自动机。而Trie图是一种确定性有限状态自动机(DFA);AC自动机、Trie图、后缀树都是一种Trie。这尼玛又开始给我去学习《编译原理》还有深入研究一下算法和数据结构的冲动…… 不过感觉这道题用了这种复杂结构,怕不是总时间少不了多少——构造ac自动机的时间怕不是就把节省的时间抵消的差不多了?但学习一些新东西也是好的。

另外一个评论区大佬有个23ms 96%的方法,学习一下:

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        
        List<Integer> res = new ArrayList<Integer>();
        if (words.length == 0) return res;
        int wl = words[0].length();//单词长度
        int wc = words.length;//单词数组容量
        int win = wc * wl; //匹配总长度。我居然没注意到题目是同等长度的子串。。。
        
        Map<String,Integer> map1 = new HashMap<String,Integer>();//map1存储<单词,重复次数>
        for (String w:words) {//遍历words数组
            if (map1.get(w)==null) map1.put(w,0);//将未收录单词存入map1
            map1.put(w, map1.get(w)+1);//出现次数+1
        }
        
        int[] wordNums = new int[map1.size()];//wordNums存储单词重复次数
        int i = 0;
        for (Integer n:map1.values()) {//这个遍历map的value的方法要学习一下,我还不怎么会用map……(捂脸)
            wordNums[i] = n;
            i++;
        }
        
        int[] f=new int[s.length()];//f中存储s位置对应单词子串的编号(优化遍历过程通过这个数组来实现的!!!)
        int wn=1;//wn就是map中对应单词的编号
        for(String w:map1.keySet()) {
            int index = -2;//方便进入循环,-2无特殊含义
            while(index != -1) {//找到一个以后,再次往后查找,直到indexOf没能找到,返回-1为止
                if (index == -2) index=-1;
                index = s.indexOf(w, index+1);//寻找字符串w(即map1存储的单词)在s中的位置
                if (index >=0) f[index] = wn;
            }
            wn++;//下一个单词,下一个编号。
        }
        
        int[] wordNumsWin = new int[map1.size()];//存储当时比较的串中各个单词的实际数量
        for (int j=0;j+win<=s.length();j++) {
            while(f[j]==0) {//f为0说明该地方没有对应的子串
                j++;
                if(j+win>s.length()) return res;
            }
            int k=j;
            while(k<j+win) {
                if(f[k] != 0) {
                    wordNumsWin[f[k]-1]++;
                    if (wordNumsWin[f[k]-1] > wordNums[f[k]-1]) break;
                }else break;
                k+=wl;//每次跳跃一个单词长度,到下一个单词
            }
            if (k==j+win) {//成功匹配了一个串之后的检查——不是很理解这里存在的意义。按道理来说,前面while循环内排除了实际数量大于words中单词数量的情况;而有一个单词实际数量小于words单词数量的话,因为总长度已经满足,必然对应一个大于words数量的单词,从而会被前面的while解决掉。
                //compare
                int mm=0;
                for (;mm<map1.size();mm++) {
                    if (wordNumsWin[mm] != wordNums[mm]) break;
                }
                if (mm==map1.size()) res.add(j);
            }
            // clean the wordNumsWin
            for (int mm=0;mm<map1.size();mm++) wordNumsWin[mm] = 0;
        }
        
        return res;
    }
}

这个答案才是真大佬呀,感觉ac自动机有点太浮夸了,读这个答案我才发现题目要求的是相同长度的子串去匹配,所以ac自动机有点杀鸡用牛刀的感觉。要是按我理解的words数组都是任意长度字符串的话,那还可以考虑用用ac自动机——但我仔细想想,直接把f[ ]数组扩充为f[ ][2]二维数组,f[ ][0]存储单词编码,f[ ][1]存储单词长度用于位移,应该就可以做到动归了吧?这个实现的确简单方便。

自己还是有点忘记去使用indexOf去找子串了…… 类库还是用的不熟练呀。

感想

贴贴自己的做的吧:

自己先实现了一个很蠢的方法:维护3个HashMap,分别为:

  • hm,存储words里面的字符串和对应的长度;
  • wordsNum,存储words里面字符串和重复次数;
  • testWordNum,存储遍历s时,已经探明的字符串和重复次数。

然后从s开头到s.length - words所有字符串总长 的区间内,试着去重复地将一个长度为words所有字符串总长的s.substring内部匹配words.

结果速度果然极其慢:

执行用时 : 330 ms, 在Substring with Concatenation of All Words的Java提交中击败了28.07% 的用户

内存消耗 : 58 MB, 在Substring with Concatenation of All Words的Java提交中击败了35.51% 的用户

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
    	List<Integer> ans = new ArrayList<>(); 
    	if(s.equals("")||words.length==0) return ans;//这个好坑,为了171/173用例: "" [];172/173用例:"a" []而添加
    	
    	int maxLen = -1;
    	int minLen = 0x3f3f3f3f;
    	int totalLen = 0;
    	int len;
    	String testS;

    	HashMap<String, Integer> hm = new HashMap<>();
    	HashMap<String, Integer> wordsNum = new HashMap<>();
    	HashMap<String, Integer> testWordsNum = new HashMap<>();
    	for(int i=0;i<words.length;i++){
    		len = words[i].length();
    		if(len>maxLen) maxLen = len;
    		if(len<minLen) minLen = len;
    		totalLen += len;
    		hm.putIfAbsent(words[i],len);
    		wordsNum.put(words[i],wordsNum.containsKey(words[i])?wordsNum.get(words[i])+1:1);
    	}
        
        for(int i=0;i<s.length()-totalLen+1;i++){
        	testWordsNum.clear();
        	int pos = i;
        	int flag = 1;
        	while(pos<i+totalLen&&flag==1){
        		flag = 0;
        		for(int j=minLen;j<=maxLen;j++){
        			if(hm.containsValue(j)){
        				testS=s.substring(pos,pos+j);
        				if(hm.containsKey(testS)&&(!testWordsNum.containsKey(testS)||testWordsNum.get(testS)<wordsNum.get(testS))){
        					if(testWordsNum.containsKey(testS)) testWordsNum.put(testS,testWordsNum.get(testS)+1);
        					else testWordsNum.put(testS,1);
        					pos+=j;
        					flag = 1;
        					break;
        				}
        			}
        		}

        	}
        	if(pos==i+totalLen){
        		ans.add(i);
        	}
        }
        return ans;
    }
}

后来发现只需要两个HashMap:

hm是多余的,但是很显然,这样的改进仅仅是杯水车薪,算法的时间复杂度和空间复杂度还仅仅是常数项的变化。

执行用时 : 287 ms, 在Substring with Concatenation of All Words的Java提交中击败了31.84% 的用户

内存消耗 : 64.9 MB, 在Substring with Concatenation of All Words的Java提交中击败了32.95% 的用户

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
    	List<Integer> ans = new ArrayList<>(); 
    	if(s.equals("")||words.length==0) return ans;//这个好坑,为了171/173用例: "" [];172/173用例:"a" []而添加
    	int maxLen = -1;
        int minLen = 0x3f3f3f3f;
    	int totalLen = 0;
        int len;
    	String testS;

    	HashMap<String, Integer> wordsNum = new HashMap<>();
    	HashMap<String, Integer> testWordsNum = new HashMap<>();
    	for(int i=0;i<words.length;i++){
    		len = words[i].length();
            if(len>maxLen) maxLen = len;
            if(len<minLen) minLen = len;
            totalLen += len;
    		wordsNum.put(words[i],wordsNum.containsKey(words[i])?wordsNum.get(words[i])+1:1);
    	}
        
        for(int i=0;i<s.length()-totalLen+1;i++){
        	testWordsNum.clear();
        	int pos = i;
        	int flag = 1;
        	while(pos<i+totalLen&&flag==1){
        		flag = 0;
        		for(int j=minLen;j<=maxLen&&j<i+totalLen-pos+1;j++){
        			testS=s.substring(pos,pos+j);
        			if(wordsNum.containsKey(testS)&&(!testWordsNum.containsKey(testS)||testWordsNum.get(testS)<wordsNum.get(testS))){
        				if(testWordsNum.containsKey(testS)) testWordsNum.put(testS,testWordsNum.get(testS)+1);
        				else testWordsNum.put(testS,1);
        				pos+=j;
        				flag = 1;
        				break;
        			}
        		}
        		

        	}
        	if(pos==i+totalLen){
        		ans.add(i);
        	}
        }
        return ans;
    }
}

最后写题解才发现题目都没审清楚。。。少了有效信息必然导致算法处理了没必要考虑的情况,而使复杂度冗余偏高呀~(根本原因还是自己没有用动归,不要找理由啦~)

资料来源 【力扣算法】30-串联所有单词的子串
博客作者 ZeromaXHe
前往答题
我的笔记