Substring with Concatenation of All Words (H)

題目

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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

題意

給定一個字串s和單詞陣列words，判斷s中是否存在一個子串，正好為words中所有單詞連起來的字串(順序不計)，

思路

暴力法：直接將每個單詞看做是一個字符進行匹配，因為單詞的順序不一定，可以用HashMap來記錄單詞和出現次數的對應關系，

\(O(N)\)優化：暴力法的缺陷在于進行了大量的重復計算，參考 LeetCode 30. Substring with Concatenation of All Words 進行優化，

代碼實作

Java

暴力

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        if (words.length == 0) {
            return new ArrayList<>();
        }
      
        int len = words[0].length(), num = words.length;
        List<Integer> list = new ArrayList<>();
        Map<String, Integer> record = new HashMap<>();
        Map<String, Integer> tmp = new HashMap<>();
      
        for (String word : words) {
            record.putIfAbsent(word, 0);
            record.put(word, record.get(word) + 1);
        }
      
        for (int i = 0; i < s.length(); i++) {
            if (s.length() - i < num * len) {
                break;
            }
          
						tmp.clear();
            int j = i;
          
            while (j - i != num * len) {
                String w = s.substring(j, j + len);
                if (!record.containsKey(w)) {
                    break;
                }
                tmp.putIfAbsent(w, 0);
                tmp.put(w, tmp.get(w) + 1);
                if (tmp.get(w) > record.get(w)) {
                    break;
                }
                j += len;
            }
          
            if (j - i == num * len) {
                list.add(i);
            }
        }
        return list;
    }
}

\(O(N)\)優化

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        if (words.length == 0) {
            return new ArrayList<>();
        }
      
        int len = words[0].length(), num = words.length;
        List<Integer> list = new ArrayList<>();
        Map<String, Integer> record = new HashMap<>();
        Map<String, Integer> tmp = new HashMap<>();
      
        for (String word : words) {
            record.putIfAbsent(word, 0);
            record.put(word, record.get(word) + 1);
        }

        for (int i = 0; i < len && i < s.length(); i++) {
            if (s.length() - i < num * len) {
                break;
            }
          
            tmp.clear();
            int left = i, right = i;
          
            while (true) {
                if (right - left == num * len) {
                    list.add(left);
                    String headW = s.substring(left, left + len);
                    tmp.put(headW, record.get(headW) - 1);
                    left += len;
                }
              
                if (s.length() - left < num * len) {
                    break;
                }
              
                String w = s.substring(right, right + len);
              
                if (!record.containsKey(w)) {
                    tmp.clear();
                    left = right + len;
                } else {
                    tmp.putIfAbsent(w, 0);
                    tmp.put(w, tmp.get(w) + 1);
                    while (tmp.get(w) > record.get(w) && s.length() - left >= num * len) {
                        String headW = s.substring(left, left + len);
                        tmp.put(headW, tmp.get(headW) - 1);
                        left += len;
                    }
                }
              
                right += len;
            }
        }

        return list;
    }
}

標籤：其他

上一篇：0029. Divide Two Integers (M)

下一篇：python筆記07