leetcode: Substring with Concatenation of All Words

问题描述：

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

原问题链接：https://leetcode.com/problems/substring-with-concatenation-of-all-words/

 

问题分析

    这个问题看起来比较难，不过实际上并不难找到合适的思路。从问题的要求来看，它是希望能找到所有的子串，这个子串由给定的一个数组里的所有字符串组成。这里有一个容易忽略的地方，就是给定的字符串数组里是可能出现有重复的元素的。所以我们可以用一个Map<String, Integer>来保存这个数组里每个元素以及它在数组里出现的个数。

　　为什么要建立这么一个map呢？因为为了保证目标串s里存在有和给定字符串数组匹配的部分。我们会从s的最开始取一个所有字符串数组长度和那么长的子串，去和这个字符串数组比较。如果符合则从它的下一个位置再去这么一个长度来比较。在比较的过程中每找到一个map里存在的元素，就将这部分从map里删除或者对应的次数减一。这样如果碰到不匹配的就可以确定这部分不匹配然后直接返回了。这样，判断一个子串和一个字符串列表是否符合就根据最后返回的这个map是否为空就可以了。

　　按照这个思路实现的代码如下：

 

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int wLen = words.length * words[0].length(), uLen = words[0].length();
        List<Integer> result = new ArrayList<>();
        Map<String, Integer> origin = createMap(words);
        for(int i = 0; i < s.length() - wLen + 1; i++) {
            Map<String, Integer> map = new HashMap<>(origin);
            for(int j = i; j < i + wLen; j += uLen) {
                String section = s.substring(j, j + uLen);
                if(map.containsKey(section)) {
                    int n = map.get(section);
                    if(--n == 0) map.remove(section);
                    else map.put(section, n);
                }
                else break;
            }
            if(map.isEmpty()) result.add(i);
        }
        return result;
    }
    
    public Map<String, Integer> createMap(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else map.put(s, 1);
        }
        return map;
    }
}

  

  　上述代码的实现虽然逻辑上是正确的，但是执行的效率并不高。它的时间复杂度为O(N ^ 2)。因为每次我们计算完s的一个子串的匹配情况，我们又要从它的下一个位置做类似的运算。这里有大量的substring的运算操作，使得整体的速度会比较慢。那么有没有办法去做一些改进并充分利用一下每次当前计算的中间结果呢？

 

改进方法

    在上述的解决方法中实际上有一个可以利用的地方。假设从索引位置i到j的这段符合原来的条件。原来的方法就是丢弃原来的结果，去看i + 1这个位置的。但是我们完全可以考虑从i + len的位置开始的情况。假设len是String[] words里一个元素的长度。因为这个时候我们要考虑的就是把i到i + len这个串去掉，然后去看后面一个len长的串是否符合条件就可以了。不需要去从头到尾的在把字符串往map里放一遍。这样可以提高不少的速度。

　　基于上述这个思路，我们不需要像前面每次从字符串s的开头到后面，只需要考虑从０到len - 1这个长度的范围。因为从０开始，我们会考虑0, 0 + len, 0 + 2 * len, ...一直到最后部分。同样，对于上述的遍历过程，还有一些细节需要细化。

    首先一个，当我们遍历了一段words里所有字符串长度和的子串时，怎么保证我们这一段是匹配的呢？在前面的方法里是用一个map保存了它们，每次碰到一个匹配的就减一或者整个去掉。因为我们这里考虑到要重用前面遍历过的部分结果，每次碰到一个匹配的就减一或者去掉就肯定不合适了。这里可以采用另外一种方式。当我们从某个位置开始去遍历的时候，就建立一个map。这个map和前面解法里定义的一样，就是没碰到一个元素的时候就往map里添加。同时也定义一个记录元素个数的变量count。这样当遍历了words.length个元素的时候也就是count == words.length。这时候表示我们遍历完了一段。当然，光有这个还是不足以判断我们遍历的这一段就和前面的map匹配。我们还需要在每次往这个本地map里添加元素的时候判断，如果出现某个元素的值比全局的那个map对应的值还要大，则表示我们匹配有误，要从当前遍历的位置开始到当前不符合的值的位置为止把这些在本地map里的元素都去掉，然后从第一次出现这个不符合的值的位置后面继续去查找匹配。

　　还有一个情况就是我们在遍历的过程中如果发现某个值根本就在全局的map里不存在。针对这种情况可以直接将遍历的起始点放到这个值的后面并将本地map清空。因为所有到这个值的串肯定不符合条件了。

　经过这些优化可以使得程序的执行效率得到很大的提升，最终的实现也会复杂很多。最终的实现如下：

 

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int num = words.length, uLen = words[0].length(), wLen = num * uLen;
        List<Integer> result = new ArrayList<>();
        Map<String, Integer> wordsMap = createMap(words);
        String[] subStrings = createSubStringList(s, wordsMap, uLen);
        for(int i = 0; i < uLen; i++) {
            int start = i, found = 0;
            Map<String, Integer> localMap = new HashMap<>();
            for(int j = i; j <= s.length() - uLen; j += uLen) {
                String word = subStrings[j];
                if(word.equals("")) {
                    localMap = new HashMap<>();
                    start = j + uLen;
                    found = 0;
                    continue;
                } else {
                    if(!localMap.containsKey(word)) localMap.put(word, 1);
                    else localMap.put(word, localMap.get(word) + 1);
                    found++;
                }
                if(localMap.get(word) > wordsMap.get(word)) {
                    while(!subStrings[start].equals(word)) {
                        localMap.put(subStrings[start], localMap.get(subStrings[start]) - 1);
                        start += uLen;
                        found--;
                    }
                    localMap.put(word, localMap.get(word) - 1);
                    start += uLen;
                    found--;
                }
                if(found == num) result.add(start);
            }
        }
        return result;
    }
    
    public Map<String, Integer> createMap(String[] words) {
        Map<String, Integer> map = new HashMap<>();
        for(String s : words) {
            if(map.containsKey(s)) {
                map.put(s, map.get(s) + 1);
            } else map.put(s, 1);
        }
        return map;
    }
    
    public String[] createSubStringList(String s, Map<String, Integer> map, int len) {
        String[] strs = new String[s.length() - len + 1];
        for(int i = 0; i < strs.length; i++) {
            String sub = s.substring(i, i + len);
            if(map.containsKey(sub)) strs[i] = sub;
            else strs[i] = "";
        }
        return strs;
    }
}

    这种实现稍微多用了一点空间。将原来数组里每个元素作为起始位置且长度为words[0]的子串放到一个字符串数组里。这样在后面的程序里需要用到时就直接取了不用再去临时算。这里的细节在于针对里面部分字符串不在全局map里，以及当本地的map出现的次数超过全局map时的处理。整个代码的时间复杂度为O(N)。

 

总结

 　　针对这种类型的问题，起始还有很多细节的优化可以做。当然，在运算中如果能够尽量的重用前面运算的结果是一种提高效率的好办法。这个问题就是一个典型的体现。