Expressive Words - Leetcode Solution

Problem Statement:

Given a list of words, we may encode it by replacing each letter with a corresponding number of occurences in the word. For example, 'aabbbc' can be encoded to '2a3b1c'. Now, given a list of encoded words, return true if and only if all the words can be encoded in the same way.

Solution:

For this problem we need to first understand the encoding process. To encode a word, we need to keep a track of all the consecutive occurrences of the same letter and record the count of that letter. After that, we concatenate the character with its count and move to the next letter. We keep on doing this until we have counted all the letters in the word.

Now, we can use this encoding process to solve the given problem. We need to check if all the given words can be encoded in the same way. To do this, we will first check if the first character of all the words is same or not. If it is not same, then we can return False as we can't encode them in the same way.

Next, we will loop through each character of the first word and check if the same character has the same frequency in all other words. If it is not same, then we need to check if the frequency is greater than or equal to 3 or not. If frequency is less than 3, then we can't encode the word in the same way.

Lastly, we need to check if the length of the words are same or not. If the lengths are not same, then we can't encode them in the same way.

If all the conditions are satisfied, then we can encode all the words in the same way and return True.

Here is the Python implementation of the solution:

class Solution: def expressiveWords(self, S: str, words: List[str]) -> int: def encode(S): encoding = [] start, end = 0, 0 while end < len(S): while end < len(S) and S[end] == S[start]: end += 1 encoding.append((S[start], end - start)) start = end return encoding

    S_encoding = encode(S)
    result = 0
    for word in words:
        word_encoding = encode(word)
        if len(S_encoding) != len(word_encoding):
            continue
        same_initial_character = True
        for i in range(len(S_encoding)):
            if S_encoding[i][0] != word_encoding[i][0]:
                same_initial_character = False
                break
            if S_encoding[i][1] < word_encoding[i][1]:
                same_initial_character = False
                break
            if S_encoding[i][1] >= word_encoding[i][1] and S_encoding[i][1] < 3:
                same_initial_character = False
                break
        if same_initial_character:
            result += 1
    return result

Time Complexity: O(N * M) where N is the number of words in the list and M is the maximum length of any word.

Space Complexity: O(1) as we are not storing any additional information other than encoding the strings.

1