algoadvance

Leetcode 824. Goat Latin

Problem Statement

The problem is to transform a sentence into Goat Latin. A sentence consists of words separated by spaces. Each word consists of lowercase and uppercase letters only.

Rules of Goat Latin:

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. For example, the first word gets “a” added to the end, the second word gets “aa” added, and so on.

Return the final sentence representing the conversion to Goat Latin.

Clarifying Questions

1. Input Constraints:
   • Are there any constraints on the length of the sentence?
     • The length of the sentence will fit within the limits of typical interview problems.
2. Sentence Structure:
   • Is the input guaranteed to be a valid sentence with words separated by spaces and each word containing only alphabetic characters?
     • Yes, we can assume valid input as per the problem statement.
3. Case Sensitivity:
   • Should the transformation be case-sensitive?
     • The transformation is case-sensitive based on the rules provided, but typically only lowercase is considered for vowel/consonant checking.

Strategy

1. Split the sentence into words using the space delimiter.
2. Iterate over each word and apply the Goat Latin transformation rules:
   • Check if the first character is a vowel.
   • If it is a vowel, append “ma”.
   • If it is a consonant, move the first letter to the end and then append “ma”.
   • Add the appropriate number of ‘a’s based on the word’s index in the sentence.
3. Join the words with spaces to form the final Goat Latin sentence.
4. Return the transformed sentence.

Code

public class GoatLatin {
    public static String toGoatLatin(String sentence) {
        // Base vowels set
        Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
        
        // Split the sentence into words
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (vowels.contains(word.charAt(0))) {
                sb.append(word);
            } else {
                sb.append(word.substring(1)).append(word.charAt(0));
            }
            sb.append("ma").append("a".repeat(i + 1));
            if (i != words.length - 1) {
                sb.append(" ");
            }
        }
        
        return sb.toString();
    }
    
    // You can use the below main method for quick testing
    public static void main(String[] args) {
        String sentence = "I speak Goat Latin";
        System.out.println(toGoatLatin(sentence)); // Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"
    }
}

Time Complexity

• Splitting the Sentence: O(n), where n is the length of the sentence.
• Processing Each Word: Each word is processed in O(m) time, where m is the length of the word.
• Total Complexity: O(n) for iterating through the sentence plus O(m) for each word transformation, leading to a final time complexity of O(n).

This approach ensures that we efficiently transform the given sentence to Goat Latin following the specified rules.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?