[LeetCode] 30. Substring with Concatenation of All Words ☆☆☆

时间:2021-02-11 06:26:10

 

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 words exactly 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).

 

解法1:

  题目要求在给定一个字符串s和一个字符串数组words(有m个字符串,长度均为n)的条件下,找出s中所有“由words中全部字符串按任意顺序串联而成”的子串。

  需要用到两个哈希表,第一个存储words数组,key为每一个word,value为出现的次数(考虑到数组中可能会有相同的字符串);第二个哈希表用于存储当前遍历到的子串,value为已出现次数。从s的第一个字符开始遍历,按顺序找到长度为n的子串part,判断part是否在第一个哈希表中,以及当前已出现次数是否超过words数组中的数量,不满足条件的跳出循环并从s的下一个字符继续寻找。

  时间复杂度为 O(n2)。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || words == null || words.length == 0) {
            return res;
        }
        
        HashMap<String, Integer> toFind = new HashMap<>();
        for (String word : words) {
            Integer k = toFind.containsKey(word) ? toFind.get(word) + 1 : 1;
            toFind.put(word, k);
        }
        
        int m = words.length, n = words[0].length();
        HashMap<String, Integer> found = new HashMap<>();
        for (int i = 0; i <= s.length() - m * n; i++) {
            found.clear();
            int j = i;
            for (; j < i + m * n; j += n) {
                String part = s.substring(j, j + n);
                Integer a = toFind.get(part);
                Integer b = found.get(part);
                if (a == null || (b != null && a <= b)) {
                    break;
                }
                found.put(part, b == null ? 1 : ++b);
            }
            if (j == i + m * n) {
                res.add(i);
            }
        }
        
        return res;
    }
}

 

解法2:

  仔细研究上面的解法,会发现其中有很多多余的步骤。例如,s="abcdefghijklmn",n=3:第一次遍历从'a'开始,需要遍历"abc", "edf", "ghi"....;而第4次比较从'd'开始,又需要遍历"def", "ghi"....

  可以改变上面的思路,从一个字符一个字符遍历,变成一个单词一个单词遍历。将s按照word的长度n进行划分,如s长度为18,m=2,n=3,那么遍历的顺序为:第一次(0,3,6,9,12,15),第二次(1,4,7,10,13,16),第三次(2,5,8,11,14,17)。

  首先还是先将words中的单词存到哈希表toFind中。然后从0开始遍历,用left记录当前串联起来的子串的起始位置,curr表示当前的子串(长为n),哈希表found纪录目前串联子串中的每一个word情况。遍历时分以下几种情况:

  • curr在toFind中不存在,此时匹配中断,前面从left开始匹配到的都失效。因此,清空found,从下一个子串(curr+n)继续。
  • curr在toFind中存在,但在found中不存在,说明前面没有匹配到。因此,将curr记入found中,然后从下一个子串继续。
  • curr在toFind和found中都存在,并且found中的数量小于toFind中的数量。将found中的currz数量加一,然后从下一个子串继续。
  • curr在toFind和found中都存在,并且两者数量相同,此时再将curr记入found就超过数量限制了。因此,需要从left开始,找到最早出现的同curr相同的子串(设为dupl),并把dupl同之前的子串在found中的纪录删除,然后从left移到dupl的下一个子串,然后curr从curr的下一个子串继续。

  每次curr操作结束后,比较当前串联子串的长度是否与与words中所有word长度之和相等,相等则说明当前串联子串匹配成功,将left记入res中,然后从left的下一个子串继续进行。。。。

  当 i = 0 遍历完成时,清空found,然后从 i = 1 进行下一次循环。

  这个算法实现难度比较大,但是整体的时间复杂度为 O(n)。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s == null || words == null || words.length == 0) {
            return res;
        }
        
        HashMap<String, Integer> toFind = new HashMap<>();
        for (String word : words) {
            Integer k = toFind.containsKey(word) ? toFind.get(word) + 1 : 1;
            toFind.put(word, k);
        }
        
        int m = words.length, n = words[0].length();
        HashMap<String, Integer> found = new HashMap<>();
        for (int first = 0; first < n; first++) {
            found.clear();
            int left = first;  // 当前串联字符串的起始位置
            for (int curr = first; curr < s.length() && left <= s.length() - m * n; curr += n) {
                String part = s.substring(curr, curr + n);
                if (!toFind.containsKey(part)) { // 如果part不存在,清空found并从下一个位置开始
                    found.clear();
                    left = curr + n;
                    continue;
                }
                
                if (!found.containsKey(part)) {
                    found.put(part, 1);
                } else if (found.get(part) < toFind.get(part)) {
                    found.put(part, found.get(part) + 1);
                } else { 
                    // found和toFind中part数量相同,再添加就超出了,因此需要从left开始,
                    // 找到第一个part相同的子串,将其与之前的子串删去,再将其下一个字符串为起点。
                    while (!part.equals(s.substring(left, left + n))) {
                        Integer x = found.get(s.substring(left, left + n));
                        found.put(s.substring(left, left + n), x - 1);
                        left += n;
                    }
                    // 此处需要从found中删除left,再添加curr,但两者相同,故可抵消
                    left += n;
                }
                
                // 如果当前串联子串的长度与数组长度相同,说明成功匹配了一个,
                // 将其记录到res后,从left的下一个子串再继续
                if (curr - left == (m - 1) * n) {
                    res.add(left);
                    Integer y = found.get(s.substring(left, left + n));
                    found.put(s.substring(left, left + n), y - 1);
                    left += n;
                }
            }
        }
        
        return res;
    }
}