如何基于子串字母表高效排序Go语言字符串切片？

问题背景 #

需要根据包含多字符“字母”的自定义字母表对单词列表排序，例如示例中的"ng"是一个优先级高于"n"的独立字母，常规逐字符匹配或整串匹配方法无法满足需求，同时需避免O(n²)级别的时间复杂度。

解决方案思路 #

核心是先将单词拆分为符合自定义字母表的序列，再基于序列中字母的优先级进行排序。关键步骤如下：

• 预处理字母表，为每个字母分配优先级排名，并按字母长度降序排列，确保优先匹配长字母；
• 实现单词拆分函数，将单词转换为自定义字母的有序序列；
• 基于拆分后的序列实现自定义比较逻辑，用于排序。

完整Go代码实现 #

package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	words := []string{"kape", "piki", "na", "nga", "bube", "babo", "ninggi", "baboninggi"}
	alphabet := []string{"a", "i", "u", "e", "o", "p", "t", "k", "m", "ng", "n", "b", "d", "g"}

	// 构建字母优先级映射，同时按长度降序排列字母（优先匹配长字母）
	letterRank := make(map[string]int)
	var sortedLetters []string
	for idx, letter := range alphabet {
		letterRank[letter] = idx
		sortedLetters = append(sortedLetters, letter)
	}
	// 按字母长度降序排序，避免短字母优先匹配导致的错误拆分
	sort.Slice(sortedLetters, func(i, j int) bool {
		return len(sortedLetters[i]) > len(sortedLetters[j])
	})

	// 自定义单词比较函数
	customCompare := func(a, b string) bool {
		// 将单词拆分为自定义字母序列
		splitA := splitIntoCustomLetters(a, sortedLetters)
		splitB := splitIntoCustomLetters(b, sortedLetters)

		// 逐个比较字母的优先级
		minSeqLen := min(len(splitA), len(splitB))
		for i := 0; i < minSeqLen; i++ {
			rankA, rankB := letterRank[splitA[i]], letterRank[splitB[i]]
			if rankA != rankB {
				return rankA < rankB
			}
		}
		// 前缀完全匹配时，短单词排在前面
		return len(splitA) < len(splitB)
	}

	// 对单词列表执行排序
	sort.Slice(words, func(i, j int) bool {
		return customCompare(words[i], words[j])
	})

	// 输出结果，与预期顺序一致
	fmt.Println(words)
	// 输出: [piki kape nga na ninggi babo baboninggi bube]
}

// splitIntoCustomLetters 按自定义字母表拆分单词，优先匹配长字母
func splitIntoCustomLetters(word string, sortedLetters []string) []string {
	var letterSeq []string
	currentStr := word
	for len(currentStr) > 0 {
		matchFound := false
		for _, letter := range sortedLetters {
			if strings.HasPrefix(currentStr, letter) {
				letterSeq = append(letterSeq, letter)
				currentStr = currentStr[len(letter):]
				matchFound = true
				break
			}
		}
		if !matchFound {
			// 处理不在字母表中的字符，可根据需求调整逻辑（如抛出错误）
			letterSeq = append(letterSeq, string(currentStr[0]))
			currentStr = currentStr[1:]
		}
	}
	return letterSeq
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

关键细节说明 #

1. 字母预处理：将字母按长度降序排列，确保拆分单词时优先识别"ng"这类长字母，避免被错误拆分为"n"+"g"。
2. 拆分函数：通过前缀匹配逐个提取自定义字母，保证拆分结果完全符合字母表定义。
3. 比较逻辑：基于拆分后的字母序列，按字母优先级逐一比较，优先级高（排名小）的字母对应的单词更靠前；前缀相同时，短单词优先。

时间复杂度分析 #

• 字母表预处理：O(m log m)（m为字母表长度，排序耗时）；
• 单词拆分：总耗时O(totalChars * m)（totalChars为所有单词的字符总数）；
• 排序阶段：O(n log n * avgSeqLen)（n为单词数量，avgSeqLen为单词拆分后的平均序列长度）；
  整体复杂度远低于O(n²)，适合处理大规模单词列表。

内容的提问来源于stack exchange，提问作者bigyihsuan