algoadvance

You are given a sentence sentence that consists 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:

1. 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”.

2. 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”.

3. Add one letter ‘a’ to the end of each word per its word index in the sentence, starting with 1. That is, 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 sentence to Goat Latin.

Example:

Input: sentence = "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Constraints:

• 1 <= sentence.length <= 150
• sentence consists of English letters and spaces.
• There will be no leading or trailing spaces.
• All words in the sentence are separated by a single space.

Clarifying Questions

1. Should the vowels be case-sensitive, treating both ‘A’ and ‘a’ as vowels?
   • Yes, both uppercase and lowercase vowels are considered as such.
2. Should we preserve the original case of the words in the final output?
   • Yes, the original case should be preserved.

Strategy

1. Split the sentence into words.
2. Iterate through each word and modify it based on the Goat Latin rules:
   • Check if the word starts with a vowel:
     • Append “ma” to the end of the word.
   • If the word starts with a consonant:
     • Move the first letter to the end and append “ma”.
   • Append the corresponding number of ‘a’ characters (based on the word’s index).
3. Join the words back into a single string with spaces and return the result.

Code

def toGoatLatin(sentence: str) -> str:
    def is_vowel(c):
        return c.lower() in 'aeiou'

    words = sentence.split()
    goat_latin_sentence = []
    
    for i, word in enumerate(words):
        suffix = 'ma' + 'a' * (i + 1)
        if is_vowel(word[0]):
            goat_latin_word = word + suffix
        else:
            goat_latin_word = word[1:] + word[0] + suffix
        
        goat_latin_sentence.append(goat_latin_word)
    
    return ' '.join(goat_latin_sentence)

# Example usage:
sentence = "I speak Goat Latin"
print(toGoatLatin(sentence))  # Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Time Complexity

• Splitting the sentence into words takes O(n), where n is the length of the sentence.
• Iterating through each word and applying the Goat Latin rules is also O(n) in the worst case.
• Joining the list of words into a single string is O(n) as well.

Thus, the overall time complexity of the function is O(n), where n is the length of the input sentence, ensuring the approach is efficient for the given constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?