时间复杂度与空间复杂度分析

我们先来看看时间复杂度的分析：

时间复杂度：O(n2)，其中 n 是字符串 sentence 的长度。虽然我们对字符串只进行了常数次遍历，但是返回的字符串长度的数量级是 O(n2) 的。考虑最坏的情况，字符串 sentence 包含 75 个单词 a，此时返回的字符串的长度为：

这四部分分别为：单词 a 的长度，添加的 m 的长度，添加的 a 的长度，空格的长度。 

再来看看空间复杂度的分析：

空间复杂度：O(n2) 或 O(n)，取决于使用的语言的字符串是否可修改。如果可以修改，我们只需要 O(n) 的空间临时存储字符串切片；如果不可以修改，我们需要 O(n2) 的空间临时存储所有单词修改后的结果。注意这里不计入返回字符串使用的空间。 

Golang

var vowels = map[byte]struct{}{'a': {}, 'e': {}, 'i': {}, 'o': {}, 'u': {}, 'A': {}, 'E': {}, 'I': {}, 'O': {}, 'U': {}}func toGoatLatin(sentence string) string {ans := &strings.Builder{}for i, cnt, n := 0, 1, len(sentence); i < n; i++ {if cnt > 1 {ans.WriteByte(' ')}start := ifor i++; i < n && sentence[i] != ' '; i++ {}cnt++if _, ok := vowels[sentence[start]]; ok {ans.WriteString(sentence[start:i])} else {ans.WriteString(sentence[start+1 : i])ans.WriteByte(sentence[start])}ans.WriteByte('m')ans.WriteString(strings.Repeat("a", cnt))}return ans.String()
}

好了，今天的文章分享就到这里了，希望对大家的学习有帮助哦！