Vấn đề từ biểu cảm (Expressive words) trong JavaScript

Đôi khi mọi người lặp lại các chữ cái để thể hiện cảm xúc mạnh, ví dụ "hello" → "heeellooo", "hi" → "hiiii". Trong các chuỗi như "heeellooo", chúng ta có các nhóm chữ cái liền kề giống nhau: "h", "eee", "ll", "ooo".

Đối với một chuỗi S cho trước, một từ truy vấn được gọi là "co giãn" (stretchy) nếu nó có thể được biến thành S bằng bất kỳ số lượng ứng dụng nào của phép mở rộng sau: chọn một nhóm gồm các ký tự c, và thêm một số ký tự c vào nhóm đó sao cho kích thước nhóm là 3 hoặc hơn.

Ví dụ, bắt đầu từ "hello", chúng ta có thể làm mở rộng trên nhóm "o" để được "hellooo", nhưng không thể được "helloo" vì nhóm "oo" có kích thước nhỏ hơn 3. Cũng có thể làm mở rộng khác như "ll" → "lllll" để được "helllllooo". Nếu S = "helllllooo", thì từ truy vấn "hello" sẽ là stretchy nhờ hai phép mở rộng này: query = "hello" → "hellooo" → "helllllooo" = S.

Cho một danh sách các từ truy vấn, chúng ta cần trả về số lượng từ là stretchy.

Ví dụ –

Nếu chuỗi đầu vào là:

const str = 'heeellooo';

Và danh sách từ là:

const words = ["hello", "hi", "helo"];

Thì đầu ra nên là:

const output = 1

Ví dụ

Mã thực hiện:

const str = 'heeellooo';
const words = ["hello", "hi", "helo"];
const extraWords = (str, words) => {
  let count = 0;
  for (let w of words) {
    let i = 0, j = 0;
    for (; i < str.length && j < w.length && w[j] === str[i];) {
      let lenS = 1, lenW = 1;
      for (; i+lenS < str.length && str[i+lenS] === str[i]; lenS++);
      for (; j+lenW < w.length && w[j+lenW] === w[j]; lenW++);
      if (lenS < lenW || lenS > lenW && lenS < 3) break;
      i += lenS; j += lenW;
    }
    if (i === str.length && j === w.length) { count++; }
  }
  return count;
}
console.log(extraWords(str, words));

Kết quả

Kết quả trong console:

1