809. Expressive Words 👎 LeetCode Solution (C++/JAVA)

 

809. Expressive Words 

-TechTalkBot

  

Problem:-

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.

Solution:-

• Time: $O(|words|\max(|\texttt{words[i]}|)$
• Space: $O(1)$

class Solution {
 public:
  int expressiveWords(string S, vector<string>& words) {
    int ans = 0;

    for (const string& word : words)
      if (isStretchy(S, word))
        ++ans;

    return ans;
  }

 private:
  bool isStretchy(const string& S, const string& word) {
    const int n = S.length();
    const int m = word.length();

    int j = 0;
    for (int i = 0; i < n; ++i)
      if (j < m && S[i] == word[j])
        ++j;
      else if (i > 1 && S[i] == S[i - 1] && S[i - 1] == S[i - 2])
        continue;
      else if (0 < i && i + 1 < n && S[i - 1] == S[i] && S[i] == S[i + 1])
        continue;
      else
        return false;

    return j == m;
  }
}

Alternate Solution:You are given 47 lines (37 sloc) 1.11 KB class Solution { public int expressiveWords(String S, String[] words) { int count = 0; char[] sChar = S.toCharArray(); for (String word : words) { char[] wChar = word.toCharArray(); if (check(sChar, wChar)) { count++; } } return count; } private boolean check(char[] s, char[] w) { int i = 0; int j = 0; while (i < s.length && j < w.length) { if (s[i] != w[j]) { return false; } int tempI = i; int tempJ = j; while (i < s.length && s[i] == s[tempI]) { i++; } while (j < w.length && w[j] == w[tempJ]) { j++; } int l1 = i - tempI; int l2 = j - tempJ; if (l1 == l2 || l1 >= 3 && l1 > l2) { continue; } return false; } return i == s.length && j == w.length; } } Other Solutions 904- Fruit Into Baskets - Leetcode Solution 202. Happy Number (LeetCode) Solution Learn Blogging Best Indian Blogs to Read