LeetCode791:自定义字符串排序

本文作者：Tyan
博客：noahsnail.com | CSDN | 简书

1. 题目描述

给定两个字符串 S 和 T，其中 S 的所有字符都是唯一的，并且 S 中的字符已经按某种特定顺序排列。你需要按照 S 中字符的顺序来重排 T 中的字符。未在 S 中出现的字符可以放在任何位置。

2. 解决方案

本题提供了两种解法，第一种方法利用了 Python 3.6 及以上版本中字典保持插入顺序的特点，第二种方法则使用了 Python 的内置排序功能。

• 解法一：使用有序字典

class Solution:
def customSortString(self, order: str, s: str) -> str:
# 创建一个根据 order 排序的字典
dict_order = {ch: [] for ch in order}
result = ''
# 遍历字符串 s，将存在于 order 中的字符放入字典，其余字符直接加入结果字符串
for ch in s:
if ch in dict_order:
dict_order[ch].append(ch)
else:
result += ch
# 将字典中的字符按顺序加入结果字符串
for val in dict_order.values():
result += ''.join(val)
return result

• 解法二：使用排序函数

class Solution:
def customSortString(self, order: str, s: str) -> str:
# 创建一个映射，记录每个字符在 order 中的位置
char_index = {char: idx for idx, char in enumerate(order)}
s1 = ''
s2 = ''
# 分离出需要排序和不需要排序的部分
for ch in s:
if ch in char_index:
s1 += ch
else:
s2 += ch
# 对需要排序的部分进行排序，并与不需要排序的部分拼接
return ''.join(sorted(s1, key=lambda ch: char_index[ch])) + s2

参考资料

1. LeetCode 791: Custom Sort String