Skip to main content

[H] Substring with Concatenation of All Words

Đề bài​

Cho một string s và một mảng words chứa các string có độ dài bằng nhau.

Một concatenated string là một string được ghép lại từ các string trong mảng words(mỗi word được dùng 1 lần duy nhất), và không quan trọng thứ tự của các word.

Hãy trả về các index trong s mà tại đó có thể tìm thấy concatenated string.

Ví dụ:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]

Giải thích: Tại index 0, có thể tìm thấy concatenated string "barfoo" là kết hợp của "bar" và "foo". Tại index 9, có thể tìm thấy concatenated string "foobar" là kết hợp của "foo" và "bar".

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

Output: []

Giải thích: Tại index 12 ta có thể tìm thấy goodbestword nhưng lại thiếu mất 1 chữ word. Vậy nên không tìm thấy concatenated string nào.

Constraints:

  • 1 <= s.length <= 104
  • 1 <= words.length <= 5000
  • 1 <= words[i].length <= 30
  • s and words[i] consist of lowercase English letters.

Phân tích​

  • Nhận thấy rằng mỗi word trong words đều phải được sử dụng, đối với những words có từ lặp lại thì nó vẫn phải được sử dụng hết. Vậy để kiểm tra xem một string có hợp lệ hay không, ta có thể đếm số lần xuất hiện của từng word trong words, sau đó so sánh với số lần xuất hiện của từng word trong string s.

  • Ta có thể sử dụng kỹ thuật sliding window để vừa kiểm tra sự tồn tại của 1 word cũng như đếm số lần xuất hiện của từng word trong.

  • Để tránh việc kiểm tra từng word trong s nhiều lần, vì word có length như nhau ta có thể sử dụng một sliding window với độ trượt là wordLength, và cũng vì word có length như nhau mà chỉ cần wordLength starting points thì ta có thể duyệt được toàn bộ các word trong s mà không bị lặp lại.

Pseudocode​

rs = [];

sLength = s.length;
wLength = words[0].length;
wCount = words.size;

for i from 0 to wLength:
  left = i;
  right = i;
  count = 0;
  map = {};
  while right + wLength <= sLength:
    word = s.substr(right, wLength);
    right += wLength;
    if word not in words:
      left = right;
      count = 0;
      map = {};
    else:
      map[word]++;
      count++;
      while map[word] > words[word]:
        map[s.substr(left, wLength)]--;
        count--;
        left += wLength;
      if count == wCount:
        rs.push(left);
        map[s.substr(left, wLength)]--;
        count--;
        left += wLength;
return rs

Solution​

class Solution {
public:
  vector<int> findSubstring(string s, vector<string> &words) {
    vector<int> result = {};

    const int sLength = s.length();
    const int wordCount = words.size();
    const int wordLength = words[0].length();

    // no result
    if (sLength < wordCount * wordLength) {
      return result;
    }

    // frequency of each word
    unordered_map<string, int> wordFreq;
    for (auto word : words) {
      wordFreq[word]++;
    }

    // Try each possible start index
    for (int i = 0; i < wordLength; i++) {
      int left = i;
      int right = i;
      int count = 0;
      unordered_map<string, int> windowWordFreq;

      // Sliding window
      while (right + wordLength <= sLength) {
        string word = s.substr(right, wordLength);
        right += wordLength;

        // not in words
        if (wordFreq.find(word) == wordFreq.end()) {
          count = 0;
          left = right;
          windowWordFreq.clear();
          // in words
        } else {
          windowWordFreq[word]++;
          count++;

          // remove exceed words
          while (windowWordFreq[word] > wordFreq[word]) {
            string leftWord = s.substr(left, wordLength);
            left += wordLength;
            windowWordFreq[leftWord]--;
            count--;
          }

          // find a result
          if (count == wordCount) {
            result.push_back(left);
            windowWordFreq[s.substr(left, wordLength)]--;
            count--;
            left += wordLength;
          }
        }
      }
    }

    return result;
  };
};