LeetCode 824: Goat Latin (Word Transform + Suffix Growth)
LeetCode 824StringSimulationToday we solve LeetCode 824 - Goat Latin.
Source: https://leetcode.com/problems/goat-latin/
English
Problem Summary
Given a sentence of words separated by single spaces, convert each word to Goat Latin: if it starts with a vowel, append "ma"; otherwise move first letter to end then append "ma". Also append i copies of 'a' for the i-th word (1-indexed).
Key Insight
This is direct simulation. For each word, perform one local transformation, then add a suffix that grows with index. A set of vowels makes first-character checks clean and case-insensitive.
Algorithm
- Split sentence by spaces into words.
- For each word at index i (starting from 1):
• If first char is vowel, keep word unchanged; else rotate first char to the end.
• Append "ma" and then "a" repeated i times.
- Join transformed words with single spaces.
Complexity Analysis
Let n be sentence length and k be word count.
Time: O(n + k^2) in the strict suffix-building model (because total appended 'a' count is 1+...+k).
Space: O(n + k^2) for output.
Common Pitfalls
- Forgetting uppercase vowels like 'A'.
- Starting suffix count from 0 instead of 1.
- Accidentally removing spaces or adding trailing spaces.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String toGoatLatin(String sentence) {
String[] words = sentence.split(" ");
String vowels = "aeiouAEIOU";
StringBuilder ans = new StringBuilder();
for (int i = 0; i < words.length; i++) {
String w = words[i];
if (vowels.indexOf(w.charAt(0)) >= 0) {
ans.append(w);
} else {
ans.append(w.substring(1)).append(w.charAt(0));
}
ans.append("ma");
for (int j = 0; j <= i; j++) ans.append('a');
if (i + 1 < words.length) ans.append(' ');
}
return ans.toString();
}
}func toGoatLatin(sentence string) string {
words := strings.Split(sentence, " ")
isVowel := func(ch byte) bool {
switch ch {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
var b strings.Builder
for i, w := range words {
if isVowel(w[0]) {
b.WriteString(w)
} else {
b.WriteString(w[1:])
b.WriteByte(w[0])
}
b.WriteString("ma")
b.WriteString(strings.Repeat("a", i+1))
if i+1 < len(words) {
b.WriteByte(' ')
}
}
return b.String()
}class Solution {
public:
string toGoatLatin(string sentence) {
unordered_set<char> vowels = {'a','e','i','o','u','A','E','I','O','U'};
stringstream ss(sentence);
string word, ans;
int idx = 1;
while (ss >> word) {
string cur;
if (vowels.count(word[0])) {
cur = word;
} else {
cur = word.substr(1) + word[0];
}
cur += "ma";
cur += string(idx, 'a');
if (!ans.empty()) ans += ' ';
ans += cur;
idx++;
}
return ans;
}
};class Solution:
def toGoatLatin(self, sentence: str) -> str:
vowels = set("aeiouAEIOU")
words = sentence.split(" ")
out = []
for i, w in enumerate(words, 1):
if w[0] in vowels:
cur = w
else:
cur = w[1:] + w[0]
cur += "ma" + ("a" * i)
out.append(cur)
return " ".join(out)var toGoatLatin = function(sentence) {
const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
const words = sentence.split(' ');
const out = [];
for (let i = 0; i < words.length; i++) {
const w = words[i];
let cur;
if (vowels.has(w[0])) {
cur = w;
} else {
cur = w.slice(1) + w[0];
}
cur += 'ma' + 'a'.repeat(i + 1);
out.push(cur);
}
return out.join(' ');
};中文
题目概述
给定一个由单个空格分隔的英文句子，需要将每个单词转换为 Goat Latin：若单词首字母是元音，直接在末尾加 "ma"；否则把首字母移到末尾再加 "ma"。另外第 i 个单词还要再追加 i 个 'a'（从 1 开始计数）。
核心思路
这是纯模拟题。逐个单词执行“首字母规则 + 固定后缀 + 递增长度后缀”即可。用元音集合判断首字母，能同时覆盖大小写。
算法步骤
- 按空格切分句子得到单词数组。
- 遍历第 i 个单词（i 从 1 开始）：
• 若首字母是元音，保持原样；否则把首字母挪到末尾。
• 追加 "ma"，再追加 i 个 'a'。
- 最后用单空格拼接所有结果。
复杂度分析
设句子长度为 n，单词数为 k。
时间复杂度：O(n + k^2)（后缀 'a' 总追加量为 1+...+k）。
空间复杂度：O(n + k^2)（输出字符串占用）。
常见陷阱
- 忘记把大写元音也当作元音处理。
- 把后缀计数从 0 开始导致答案少一个 'a'。
- 拼接时多空格或少空格。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String toGoatLatin(String sentence) {
String[] words = sentence.split(" ");
String vowels = "aeiouAEIOU";
StringBuilder ans = new StringBuilder();
for (int i = 0; i < words.length; i++) {
String w = words[i];
if (vowels.indexOf(w.charAt(0)) >= 0) {
ans.append(w);
} else {
ans.append(w.substring(1)).append(w.charAt(0));
}
ans.append("ma");
for (int j = 0; j <= i; j++) ans.append('a');
if (i + 1 < words.length) ans.append(' ');
}
return ans.toString();
}
}func toGoatLatin(sentence string) string {
words := strings.Split(sentence, " ")
isVowel := func(ch byte) bool {
switch ch {
case 'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U':
return true
default:
return false
}
}
var b strings.Builder
for i, w := range words {
if isVowel(w[0]) {
b.WriteString(w)
} else {
b.WriteString(w[1:])
b.WriteByte(w[0])
}
b.WriteString("ma")
b.WriteString(strings.Repeat("a", i+1))
if i+1 < len(words) {
b.WriteByte(' ')
}
}
return b.String()
}class Solution {
public:
string toGoatLatin(string sentence) {
unordered_set<char> vowels = {'a','e','i','o','u','A','E','I','O','U'};
stringstream ss(sentence);
string word, ans;
int idx = 1;
while (ss >> word) {
string cur;
if (vowels.count(word[0])) {
cur = word;
} else {
cur = word.substr(1) + word[0];
}
cur += "ma";
cur += string(idx, 'a');
if (!ans.empty()) ans += ' ';
ans += cur;
idx++;
}
return ans;
}
};class Solution:
def toGoatLatin(self, sentence: str) -> str:
vowels = set("aeiouAEIOU")
words = sentence.split(" ")
out = []
for i, w in enumerate(words, 1):
if w[0] in vowels:
cur = w
else:
cur = w[1:] + w[0]
cur += "ma" + ("a" * i)
out.append(cur)
return " ".join(out)var toGoatLatin = function(sentence) {
const vowels = new Set(['a','e','i','o','u','A','E','I','O','U']);
const words = sentence.split(' ');
const out = [];
for (let i = 0; i < words.length; i++) {
const w = words[i];
let cur;
if (vowels.has(w[0])) {
cur = w;
} else {
cur = w.slice(1) + w[0];
}
cur += 'ma' + 'a'.repeat(i + 1);
out.push(cur);
}
return out.join(' ');
};
Comments