What is the best approach to solve the Custom Sort String problem?

The optimal solution uses a hash table to store the custom order and applies it to sort string `s` efficiently.

What are the time and space complexities for Custom Sort String?

Time complexity is O(N) and space complexity is O(N), where N is the length of the input string `s`.

How do I handle characters not in the custom order in Custom Sort String?

Characters not found in `order` can be placed anywhere in the result string after sorting the characters from `order`.

What is the key to solving the Custom Sort String problem efficiently?

Efficiently solving the problem relies on using a hash table for quick lookup and sorting based on that table.

Can multiple valid outputs exist for the Custom Sort String problem?

Yes, multiple valid outputs are possible as long as the order of characters in `s` respects the custom order from `order`.

#791

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

自定义字符串排序

给定两个字符串 order 和 s 。 order 的所有字母都是唯一的，并且预先按照一些自定义的顺序排序。对 s 的字符进行置换，使其与排序的 order 相匹配。更具体地说，如果在 order 中的字符 x 出现字符 y 之前，那么在排列后的字符串中， x 也应该出现在 y 之前。返回 …

哈希表字符串排序

题目描述

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

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

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

示例 1：

输入： order = "cba", s = "abcd"

输出： "cbad"

解释： "a"，"b"，"c" 在 order 中出现，所以 "a"，"b"，"c" 的顺序应该是 "c"，"b"，和 "a"。

由于 "d" 没有在 order 中出现，它可以在返回字符串的任意位置。"dcba"，"cdba"，"cbda" 也是合法的输出。

示例 2：

输入： order = "bcafg", s = "abcd"

输出： "bcad"

解释：order 中的字符 "b"、"c" 和 "a" 决定了 s 中字符的顺序。s 中的字符 "d" 没有出现在 order 中，因此其位置是可变的。

按照 order 中的出现顺序，"b"、"c" 和 "a" 应该按 "b"、"c"、"a" 的顺序排列。"d" 可以放在任何位置，因为它不受顺序限制。输出 "bcad" 正确遵循了这一规则。其他排列如 "dbca" 或 "bcda" 也是合法的，只要 "b"、"c"、"a" 的顺序保持不变。

提示:

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

lightbulb

解题思路

方法一：自定义排序

一种比较直接的思路是，用哈希表或数组 $d$ 记录字符串 $order$ 中每个字符的位置，然后对字符串 $s$ 中每个字符按照其在 $d$ 中的位置进行排序。如果某个字符不在 $d$ 中，我们可以将其位置置为 $0$ 。

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

1

2

3

4

5

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        d = {c: i for i, c in enumerate(order)}
        return ''.join(sorted(s, key=lambda x: d.get(x, 0)))

speed

复杂度分析

指标	值
时间	O(N)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Ability to handle custom sorting logic efficiently.
question_mark
Understanding of how hash tables can be used for fast lookups.
question_mark
Clarity in explaining sorting and how to handle characters not in the custom order.

warning

常见陷阱

外企场景

error
Incorrectly handling characters not in the custom order by placing them in fixed positions.
error
Failing to consider that only characters in `order` should be ordered, and others can appear in any arrangement.
error
Overcomplicating the problem by attempting to sort non-existent or non-required elements.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using a more complex sorting algorithm instead of hash table-based indexing.
arrow_right_alt
Implementing this solution with more constraints, such as additional characters or mixed order sets.
arrow_right_alt
Handling non-lowercase characters, which may change how the hash table and sorting logic are implemented.

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #767 重构字符串 #833 字符串中的查找与替换