Goat Latin - Leetcode Solution

Goat Latin is a problem on LeetCode where we are given a sentence and we have to translate it into Goat Latin based on the rules given. The problem statement is as follows:

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.) The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word. For example, the word 'apple' becomes 'applema'.

If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma". For example, the word "goat" becomes "oatgma".

Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1. For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Let's discuss the approach to solve this problem:

1. We first split the sentence into a list of words.
2. We then iterate through each word in the list and check if the first character is a vowel or not.
   1. If it is a vowel, we add the suffix "ma" to the end of the word.
   2. If it is not a vowel, we remove the first letter and append it to the end of the word and then add the suffix "ma" to it.
3. We then add the required number of 'a' at the end of each word based on its index in the list.
4. Finally, we join the list of words to form the final sentence.

Here is the Python code for the above approach:

def toGoatLatin(S: str) -> str:
    vowels = set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])
    words = S.split()
    for i in range(len(words)):
        if words[i][0] in vowels:
            words[i] = words[i] + 'ma'
        else:
            words[i] = words[i][1:] + words[i][0] + 'ma'
        words[i] = words[i] + 'a'*(i+1)
    return ' '.join(words)

Let's discuss the time complexity of the above algorithm:

1. Splitting the sentence into a list of words takes O(n) time complexity, where n is the number of words in the sentence.
2. Iterating through each word and modifying it takes O(n) time complexity, where n is the number of words in the sentence.
3. Joining the list of words to form the final sentence takes O(n) time complexity, where n is the number of words in the sentence.
4. Therefore, the overall time complexity of the algorithm is O(n).

So, this is the detailed solution for the Goat Latin problem on LeetCode.

1