Đếm chuỗi con khớp trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một chuỗi str làm đối số thứ nhất, và một mảng chuỗi arr làm đối số thứ hai. Hàm phải đếm và trả về số lượng arr[i] là dãy con (subsequence) của chuỗi str.

Ví dụ, nếu đầu vào là:

Đầu vào

const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];

Đầu ra

const output = 3;

Giải thích

Vì các chuỗi yêu cầu là 'k', 'klp', và 'klo'.

Ví dụ

Dưới đây là mã thực hiện:

const str = 'klmnop';
const arr = ['k', 'll', 'klp', 'klo'];
const countSubstrings = (str = '', arr = []) => {
  const map = arr.reduce((acc, val, ind) => {
    const c = val[0];
    acc[c] = acc[c] || [];
    acc[c].push([ind, 0]);
    return acc;
  }, {});
  let num = 0;
  for (let i = 0; i < str.length; i++) {
    if (map[str[i]] !== undefined) {
      const list = map[str[i]];
      map[str[i]] = undefined;
      list.forEach(([wordIndex, charIndex]) => {
        if (charIndex === arr[wordIndex].length - 1) {
          num += 1;
        } else {
          const nextChar = arr[wordIndex][charIndex + 1];
          map[nextChar] = map[nextChar] || [];
          map[nextChar].push([wordIndex, charIndex + 1]);
        }
      });
    }
  }
  return num;
};
console.log(countSubstrings(str, arr));

Kết quả

3