LeetCode 824: Goat Latin

Problem Restatement

We are given a sentence made of words separated by single spaces.

Each word contains only uppercase and lowercase English letters.

We need to convert every word into Goat Latin using these rules:

1. If a word starts with a vowel, append "ma".
2. If a word starts with a consonant, move the first letter to the end, then append "ma".
3. Append 'a' characters based on the word position. The first word gets "a", the second gets "aa", the third gets "aaa", and so on.

The vowel check is case-insensitive. The vowels are:

a, e, i, o, u

The official examples include "I speak Goat Latin" converting to "Imaa peaksmaaa oatGmaaaa atinLmaaaaa".

Input and Output

Examples

Example 1:

sentence = "I speak Goat Latin"

Word by word:

The answer is:

"Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

sentence = "The quick brown fox jumped over the lazy dog"

The answer is:

"heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

First Thought: Process Each Word

The rules apply independently to each word.

So we can:

1. Split the sentence into words.
2. Convert each word.
3. Join the converted words with spaces.

There is no need for recursion, dynamic programming, or a complex data structure.

Key Insight

Only the first character of each word decides the main transformation.

If it is a vowel, the word stays in the same order.

If it is a consonant, the first character moves to the end.

After that, every word receives "ma" and a position-based suffix of 'a'.

Algorithm

Create a vowel set:

vowels = {"a", "e", "i", "o", "u"}

Split the sentence:

words = sentence.split()

For each word at index i:

1. If the first character is a vowel after lowercasing:

word[0].lower() in vowels

keep the word as is.

2. Otherwise, move the first character to the end:

word = word[1:] + word[0]

3. Append:

"ma" + "a" * (i + 1)

4. Store the converted word.

Finally, join the results with spaces.

Correctness

The algorithm processes the sentence word by word in original order.

For each word, it checks the first character case-insensitively. If the first character is a vowel, it appends "ma" without changing the word order, exactly as required.

If the first character is a consonant, it removes that character from the front and appends it to the end before adding "ma", exactly as required.

The algorithm uses the zero-based index i, so the number of appended 'a' characters is i + 1. This matches the one-based word position rule.

Since every word is transformed according to all three rules and the transformed words are joined with spaces in the same order, the returned sentence is the correct Goat Latin sentence.

Complexity

Let n = len(sentence).

Implementation

class Solution:
    def toGoatLatin(self, sentence: str) -> str:
        vowels = {"a", "e", "i", "o", "u"}
        result = []

        for i, word in enumerate(sentence.split()):
            if word[0].lower() not in vowels:
                word = word[1:] + word[0]

            word += "ma"
            word += "a" * (i + 1)

            result.append(word)

        return " ".join(result)

Code Explanation

The vowel set stores lowercase vowels only:

vowels = {"a", "e", "i", "o", "u"}

We lowercase only the first character during the check:

word[0].lower() not in vowels

This handles both uppercase and lowercase words.

For consonant-starting words, we move the first character to the end:

word = word[1:] + word[0]

Then every word receives "ma":

word += "ma"

The position suffix is based on i + 1:

word += "a" * (i + 1)

Finally, the transformed words are joined with one space:

return " ".join(result)

Testing

def run_tests():
    s = Solution()

    assert s.toGoatLatin(
        "I speak Goat Latin"
    ) == "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

    assert s.toGoatLatin(
        "The quick brown fox jumped over the lazy dog"
    ) == "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

    assert s.toGoatLatin("Apple") == "Applemaa"
    assert s.toGoatLatin("goat") == "oatgmaa"
    assert s.toGoatLatin("a b c") == "amaa bmaaa cmaaaa"

    print("all tests passed")

run_tests()