【2022-11-13每日一题】791. 自定义字符串排序[Medium]

2022-11-13每日一题：791. 自定义字符串排序

难度：Medium

标签：哈希表 、 字符串 、 排序

给定两个字符串 order 和 s 。order 的所有单词都是 唯一 的，并且以前按照一些自定义的顺序排序。

对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。

返回 满足这个性质的 s 的任意排列 。

示例 1:

输入: order = "cba", s = "abcd"
输出: "cbad"
解释: 
“a”、“b”、“c”是按顺序出现的，所以“a”、“b”、“c”的顺序应该是“c”、“b”、“a”。
因为“d”不是按顺序出现的，所以它可以在返回的字符串中的任何位置。“dcba”、“cdba”、“cbda”也是有效的输出。

示例 2:

输入: order = "cbafg", s = "abcd"
输出: "cbad"

提示:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order 和 s 由小写英文字母组成
• order 中的所有字符都 不同

方法一：哈希表 + 按字母索引排序

// 写法一
func customSortString(order string, s string) string {
    n := len(order)
    ht := make(map[byte]int, n) // 此处可以用 [26]int{} 代替
    for i := 0; i < n; i++ {
        ht[order[i]] = i
    }
    ss := []byte(s)
    sort.Slice(ss, func(i, j int) bool {
        a, b := ss[i], ss[j]
        return ht[a] < ht[b]
    })
    return string(ss)
}

// 写法二
func customSortString(order string, s string) string {
    n := len(order)
    ht := make(map[byte]int, n)
    for i := 0; i < n; i++ {
        ht[order[i]] = i + 1
    }
    ss := []byte(s)
    sort.Slice(ss, func(i, j int) bool {
        a, b := ht[ss[i]], ht[ss[j]]
        if a == 0 {
            a = int(ss[i])
        }
        if b == 0 {
            b = int(ss[j])
        }
        return a < b
    })
    return string(ss)
}

// 写法三
func customSortString(order string, s string) string {
    ht := make(map[byte]int, len(order)) // 此处可以用 [26]int{} 代替
    for i, c := range order {
        ht[byte(c)] = i
    }
    ss := []byte(s)
    sort.Slice(ss, func(i, j int) bool {
        return ht[ss[i]] < ht[ss[j]]
    })
    return string(ss)
}

复杂度分析

• 时间复杂度 O(m+n×logn)。
• 空间复杂度 O(m)。
• 其中 m 和 n 分别是字符串 order 和 s 的长度。

方法二：计数排序

// 写法一
func customSortString(order string, s string) string {
    // 计数
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    ans := make([]rune, 0, len(s))
    for _, c := range order {
        for ; cnt[c-'a'] > 0; cnt[c-'a']-- {
            ans = append(ans, c)
        }
    }
    //for _, c := range s {
    //    for ; cnt[c-'a'] > 0; cnt[c-'a']-- {
    //        ans = append(ans, c)
    //    }
    //}
    for i, c := range cnt {
        for j := 0; j < c; j++ {
            ans = append(ans, rune(i+'a'))
        }
    }
    return string(ans)
}

// 写法二
func customSortString(order string, s string) string {
    // 计数
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    t := &strings.Builder{}
    for _, c := range order {
        if cnt[c-'a'] > 0 {
            t.WriteString(strings.Repeat(string(c), cnt[c-'a']))
            cnt[c-'a'] = 0
        }
    }
    for i, k := range cnt {
        if k > 0 {
            t.WriteString(strings.Repeat(string('a'+i), k))
        }
    }
    return t.String()
}

复杂度分析

• 时间复杂度 O(m+n)。
• 空间复杂度 O(m)。
• 其中 m 和 n 分别是字符串 order 和 s 的长度。

LeetCode题库地址

• https://leetcode.cn/problems/custom-sort-string