“This is the 18th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

This article introduces the algorithm: “Emotional text”

  • What is “emotional writing”?

Sometimes people repeat letters to indicate extra feelings, such as “hello” -> “heeellooo”, “hi” -> “hiii”. We define a string of characters with the same adjacent letters as the same letter group, for example: “h”, “eee”, “ll”, “ooo”.

For a given string S, if another word can be made the same as S by stretching out some letter groups, we define it as stretchy.

The expansion operation is defined as follows: Select a letter group (including the letter C) and add the same letter C to it to make it 3 or more in length.

For example, in the case of “hello”, we can expand the letter group “o” to get “hellooo”, but we cannot do the same to get “helloo” because the letter group “oo” is less than 3.

In addition, we can do another extension “ll” -> “LLLLL” to get “helllllooo”. If S = “helllllooo”, then the query word “hello” is expandable, because both expansion operations can be performed on it such that query = “hello” -> “hellooo” -> “helllllooo” = S.

Enter a list of query words and print the number of words that can be expanded.

Example: Input: S = "heeellooo" Words = ["hello", "hi", "helo"] Output: 1 Explanation: We can get "heeellooo" by expanding the "e" and "o" of "hello". We can't get "heeellooo" by expanding "helo" because "ll" is less than 3.Copy the code

Tip:

  • 0 <= len(S) <= 100.
  • 0 <= len(words) <= 100.
  • 0 <= len(words[I]) <= 100.
  • The S and all the words in Words are made up only of lowercase letters.

JavaScript implementation:

Double pointer solution:

var expressiveWords = function (s, words) { let ans = 0; for (const w of words) if (check(s, w)) ans++; return ans; }; function check(s1, s2) { let i = s1.length - 1, j = s2.length - 1; While (I >= 0 &&j >= 0) {// if (s1[I]! == s2[j]) return false; S1 [I] let k = I, cnt1 = 0; while (s1[i] === s1[k]) i--, cnt1++; S2 [j] let h = j, cnt2 = 0; while (s2[j] === s2[h]) j--, cnt2++; If (cnt2 > cnt1) return false; // if (cnt2 > cnt1) return false; If (cnt1 === 2 && cnt2 === 1) return false; if (cnt1 === 2 && cnt2 === 1) return false; } return i === j; }Copy the code

I’m Nuggets Anthony, output exposure input, technical insight into life, goodbye ~