Bài 30 Leetcode: Substring with Concatenation of All Words

Đề bài:

Cho một chuỗi s và một mảng các chuỗi words. Tất cả các chuỗi trong mảng words có cùng độ dài.

Một chuỗi con nối trong s là một chuỗi con chứa tất cả các chuỗi của bất kỳ hoán vị nào của words được nối lại.

• Ví dụ, nếu words = [“ab”, “cd”, “ef”], thì “abcdef”, “abefcd”, “cdabef”, “cdefab”, “efabcd” và “efcdab” đều là các chuỗi con nối. “acdbef” không phải là một chuỗi con nối vì nó không phải là sự nối của bất kỳ hoán vị nào của words.

Trả về chỉ mục bắt đầu của tất cả các chuỗi con nối trong s. Bạn có thể trả về kết quả theo bất kỳ thứ tự nào.

Ví dụ 1:

Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Giải thích: Vì words.length == 2 và words[i].length == 3, nên chuỗi con nối phải có độ dài là 6.
Chuỗi con bắt đầu từ vị trí 0 là "barfoo". Nó là sự nối của ["bar", "foo"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 9 là "foobar". Nó là sự nối của ["foo", "bar"] và là một hoán vị của words.
Thứ tự đầu ra không quan trọng. Trả về [0,9] cũng đúng.

Ví dụ 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Giải thích: Vì words.length == 4 và words[i].length == 4, nên chuỗi con nối phải có độ dài là 16.
Không có chuỗi con có độ dài 16 trong s mà bằng với sự nối của bất kỳ hoán vị nào của words.
Chúng ta trả về một mảng rỗng.

Ví dụ 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Giải thích: Vì words.length == 3 và words[i].length == 3, nên chuỗi con nối phải có độ dài là 9.
Chuỗi con bắt đầu từ vị trí 6 là "foobarthe". Nó là sự nối của ["foo","bar","the"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 9 là "barthefoo". Nó là sự nối của ["bar","the","foo"] và là một hoán vị của words.
Chuỗi con bắt đầu từ vị trí 12 là "thefoobar". Nó là sự nối của ["the","foo","bar"] và là một hoán vị của words.

Ràng buộc:

• 1 <= độ dài của chuỗi s <= 10^4
• 1 <= số lượng từ trong mảng words <= 5000
• 1 <= độ dài của từ words[i] <= 30
• s và words[i] chỉ chứa các ký tự tiếng Anh viết thường.

Giải thích thuật toán bằng C++

class Solution {
 public:
  vector<int> findSubstring(string s, vector<string>& words) {
    if (s.empty() || words.empty())
      return {};

    const int k = words.size();
    const int n = words[0].length();
    vector<int> ans;
    unordered_map<string, int> count;

    for (const string& word : words)
      ++count[word];

    for (int i = 0; i < s.length() - k * n + 1; ++i) {
      unordered_map<string, int> seen;
      int j;
      for (j = 0; j < k; ++j) {
        const string& word = s.substr(i + j * n, n);
        if (++seen[word] > count[word])
          break;
      }
      if (j == k)
        ans.push_back(i);
    }

    return ans;
  }
};

Đây là một đoạn code C++ để tìm các chỉ mục bắt đầu của các chuỗi con nối trong chuỗi s. Dưới đây là một giải thích về thuật toán trong đoạn code:

1. Kiểm tra xem chuỗi s hoặc mảng words có rỗng không. Nếu có, trả về một mảng rỗng.

2. Khởi tạo các biến k và n. Biến k đại diện cho số lượng từ trong mảng words, và biến n đại diện cho độ dài của mỗi từ trong words. Đây là những thông số quan trọng để xác định độ dài của chuỗi con nối.

3. Khởi tạo một vector ans để lưu trữ các chỉ mục bắt đầu của chuỗi con nối.

4. Khởi tạo một unordered_map count để đếm số lượng từ xuất hiện trong words. Với mỗi từ trong words, tăng giá trị tương ứng trong unordered_map count lên 1.

5. Sử dụng vòng lặp for để duyệt qua các vị trí trong chuỗi s để tìm chuỗi con nối. Tham số i đại diện cho chỉ mục bắt đầu của chuỗi con nối. Vòng lặp chạy từ 0 đến độ dài của chuỗi s trừ đi k * n + 1, với k là số lượng từ trong words và n là độ dài của từ trong words.

6. Trong vòng lặp, khởi tạo một unordered_map seen để đếm số lượng từ xuất hiện trong chuỗi con nối hiện tại. Biến j được sử dụng để đánh dấu số lượng từ hợp lệ đã được tìm thấy trong chuỗi con nối.

7. Trong vòng lặp for lồng nhau, duyệt qua từng từ trong words. Sử dụng hàm substr để trích xuất từ tại vị trí i + j * n với độ dài n. Kiểm tra từ này có xuất hiện nhiều hơn số lần cho phép trong unordered_map count không. Nếu có, thoát khỏi vòng lặp.

8. Nếu biến j sau vòng lặp for lồng nhau bằng k, tức là đã tìm thấy một chuỗi con nối hợp lệ, thêm chỉ mục bắt đầu i vào vector ans.

9. Trả về vector ans chứa các chỉ mục bắt đầu của các chuỗi con nối hợp lệ trong chuỗi s.

Đây là một thuật toán tương đối đơn giản và hiệu quả để giải quyết bài toán tìm chuỗi con nối trong một chuỗi cho trước.

Giải thích thuật toán bằng Java

class Solution {
  public List<Integer> findSubstring(String s, String[] words) {
    if (s.isEmpty() || words.length == 0)
      return new ArrayList<>();

    final int k = words.length;
    final int n = words[0].length();
    List<Integer> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();

    for (final String word : words)
      count.merge(word, 1, Integer::sum);

    for (int i = 0; i <= s.length() - k * n; ++i) {
      Map<String, Integer> seen = new HashMap<>();
      int j = 0;
      for (; j < k; ++j) {
        final String word = s.substring(i + j * n, i + j * n + n);
        seen.merge(word, 1, Integer::sum);
        if (seen.get(word) > count.getOrDefault(word, 0))
          break;
      }
      if (j == k)
        ans.add(i);
    }

    return ans;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if len(s) == 0 or words == []:
      return []

    k = len(words)
    n = len(words[0])
    ans = []
    count = collections.Counter(words)

    for i in range(len(s) - k * n + 1):
      seen = collections.defaultdict(int)
      j = 0
      while j < k:
        word = s[i + j * n: i + j * n + n]
        seen[word] += 1
        if seen[word] > count[word]:
          break
        j += 1
      if j == k:
        ans.append(i)

    return ans