LeetCode 809: Expressive Words Solution

Master LeetCode problem 809 (Expressive Words), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

809. Expressive Words

Medium

Array Two Pointers String

Problem Explanation

Explanation:

To solve this problem, we can iterate through each query word and check if it can be stretched to match the given string s. We can do this by iterating over both s and the query word simultaneously, keeping track of the characters in groups and their counts. We will compare the characters and group counts between the string s and the query word to determine if the query word is stretchy.

We will use two pointers, one for the string s and one for the query word.
We will maintain variables to keep track of the group characters and their counts in both s and the query word.
We will compare the characters and their counts, ensuring that the query word can be stretched to match s.
If the query word can be stretched, we increment the count of stretchy words.

Time Complexity: O(n*m) where n is the length of string s and m is the average length of words in the query array. Space Complexity: O(1)

Solution Code

class Solution {
    public int expressiveWords(String s, String[] words) {
        int count = 0;
        for (String word : words) {
            if (isStretchy(s, word)) {
                count++;
            }
        }
        return count;
    }
    
    private boolean isStretchy(String s, String word) {
        int i = 0, j = 0;
        
        while (i < s.length() && j < word.length()) {
            char ch1 = s.charAt(i);
            char ch2 = word.charAt(j);
            
            if (ch1 != ch2) {
                return false;
            }
            
            int start1 = i;
            int start2 = j;
            
            while (i < s.length() && s.charAt(i) == ch1) {
                i++;
            }
            
            while (j < word.length() && word.charAt(j) == ch2) {
                j++;
            }
            
            int len1 = i - start1;
            int len2 = j - start2;
            
            if (len1 < 3 && len1 != len2) {
                return false;
            }
        }
        
        return i == s.length() && j == word.length();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 809 (Expressive Words)?

This page provides optimized solutions for LeetCode problem 809 (Expressive Words) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 809 (Expressive Words)?

The time complexity for LeetCode 809 (Expressive Words) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 809 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 809 in Java, C++, or Python.

Back to LeetCode Solutions