809. Expressive Words

Description

Sometimes people repeat letters to represent extra feeling. For example:

• "hello" -> "heeellooo"
• "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

• For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

 

Example 1:

Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

Example 2:

Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output: 3

 

Constraints:

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s and words[i] consist of lowercase letters.

Solutions

Solution 1: Traversal Counting + Two Pointers

We can traverse the array \(\textit{words}\), and for each word \(t\) in the array, check if \(t\) can be expanded to obtain \(s\). If it can, increment the answer by one.

Therefore, the key problem is to determine if the word \(t\) can be expanded to obtain \(s\). We use a function \(\textit{check}(s, t)\) to determine this. The implementation logic of the function is as follows:

First, check the length relationship between \(s\) and \(t\). If the length of \(t\) is greater than \(s\), return \(\textit{false}\) directly. Otherwise, use two pointers \(i\) and \(j\) to point to \(s\) and \(t\), respectively, both initially set to \(0\).

If the characters pointed to by \(i\) and \(j\) are different, then \(t\) cannot be expanded to obtain \(s\), and we return \(\textit{false}\). Otherwise, we need to check the relationship between the consecutive occurrence counts of the characters pointed to by \(i\) and \(j\), denoted as \(c_1\) and \(c_2\). If \(c_1 \lt c_2\) or \(c_1 \lt 3\) and \(c_1 \neq c_2\), then \(t\) cannot be expanded to obtain \(s\), and we return \(\textit{false}\). Otherwise, move \(i\) and \(j\) to the right by \(c_1\) and \(c_2\) times, respectively, and continue checking.

If both \(i\) and \(j\) reach the end of the strings, then \(t\) can be expanded to obtain \(s\), and we return \(\textit{true}\). Otherwise, we return \(\textit{false}\).

The time complexity is \(O(n \times m + \sum_{i=0}^{m-1} w_i)\), where \(n\) and \(m\) are the lengths of the string \(s\) and the array \(\textit{words}\), respectively, and \(w_i\) is the length of the \(i\)-th word in the array \(\textit{words}\).

Python3JavaC++Go

class Solution:
    def expressiveWords(self, s: str, words: List[str]) -> int:
        def check(s, t):
            m, n = len(s), len(t)
            if n > m:
                return False
            i = j = 0
            while i < m and j < n:
                if s[i] != t[j]:
                    return False
                k = i
                while k < m and s[k] == s[i]:
                    k += 1
                c1 = k - i
                i, k = k, j
                while k < n and t[k] == t[j]:
                    k += 1
                c2 = k - j
                j = k
                if c1 < c2 or (c1 < 3 and c1 != c2):
                    return False
            return i == m and j == n

        return sum(check(s, t) for t in words)

class Solution {
    public int expressiveWords(String s, String[] words) {
        int ans = 0;
        for (String t : words) {
            if (check(s, t)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean check(String s, String t) {
        int m = s.length(), n = t.length();
        if (n > m) {
            return false;
        }
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s.charAt(i) != t.charAt(j)) {
                return false;
            }
            int k = i;
            while (k < m && s.charAt(k) == s.charAt(i)) {
                ++k;
            }
            int c1 = k - i;
            i = k;
            k = j;
            while (k < n && t.charAt(k) == t.charAt(j)) {
                ++k;
            }
            int c2 = k - j;
            j = k;
            if (c1 < c2 || (c1 < 3 && c1 != c2)) {
                return false;
            }
        }
        return i == m && j == n;
    }
}

class Solution {
public:
    int expressiveWords(string s, vector<string>& words) {
        auto check = [](string& s, string& t) -> int {
            int m = s.size(), n = t.size();
            if (n > m) return 0;
            int i = 0, j = 0;
            while (i < m && j < n) {
                if (s[i] != t[j]) return 0;
                int k = i;
                while (k < m && s[k] == s[i]) ++k;
                int c1 = k - i;
                i = k, k = j;
                while (k < n && t[k] == t[j]) ++k;
                int c2 = k - j;
                j = k;
                if (c1 < c2 || (c1 < 3 && c1 != c2)) return 0;
            }
            return i == m && j == n;
        };

        int ans = 0;
        for (string& t : words) ans += check(s, t);
        return ans;
    }
};

func expressiveWords(s string, words []string) (ans int) {
    check := func(s, t string) bool {
        m, n := len(s), len(t)
        if n > m {
            return false
        }
        i, j := 0, 0
        for i < m && j < n {
            if s[i] != t[j] {
                return false
            }
            k := i
            for k < m && s[k] == s[i] {
                k++
            }
            c1 := k - i
            i, k = k, j
            for k < n && t[k] == t[j] {
                k++
            }
            c2 := k - j
            j = k
            if c1 < c2 || (c1 != c2 && c1 < 3) {
                return false
            }
        }
        return i == m && j == n
    }
    for _, t := range words {
        if check(s, t) {
            ans++
        }
    }
    return ans
}

Comments