Medium

题目描述

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

对 s 的字符进行排列，使其匹配 order 的排序顺序。更具体地说，如果字符 x 在 order 中出现在字符 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 中的出现顺序，s 中的 "b"、"c"、"a" 应该排列为 "b"、"c"、"a"。"d" 可以放在任意位置，因为它不在 order 中。输出 "bcad" 正确地遵循了这个规则。其他排列如 "dbca" 或 "bcda" 也是有效的，只要 "b"、"c"、"a" 保持它们的顺序。

约束：

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

解题思路

这道题的核心思路是按照 order 中定义的自定义顺序来排列字符串 s 中的字符。

解法一：计数 + 构造（推荐）

  1. 首先统计字符串 s 中每个字符的出现次数
  2. 按照 order 中字符的顺序，依次将对应的字符添加到结果中
  3. 最后将不在 order 中的字符添加到结果末尾

这种方法的时间复杂度是 O(n + m)，其中 n 是字符串 s 的长度，m 是 order 的长度。

解法二：自定义排序 可以使用自定义比较函数对字符串 s 进行排序，但这种方法的时间复杂度是 O(n log n)，效率不如解法一。

由于题目保证 order 中的字符都是唯一的，且最多只有 26 个小写字母，所以计数方法是最优解。

代码实现

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> count(26, 0);
        
        // 统计s中每个字符的出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string result = "";
        
        // 按order中的顺序添加字符
        for (char c : order) {
            while (count[c - 'a'] > 0) {
                result += c;
                count[c - 'a']--;
            }
        }
        
        // 添加不在order中的字符
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                result += (char)('a' + i);
                count[i]--;
            }
        }
        
        return result;
    }
};

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        from collections import Counter
        
        # 统计s中每个字符的出现次数
        count = Counter(s)
        result = []
        
        # 按order中的顺序添加字符
        for char in order:
            if char in count:
                result.extend([char] * count[char])
                del count[char]
        
        # 添加不在order中的字符
        for char, freq in count.items():
            result.extend([char] * freq)
        
        return ''.join(result)

public class Solution {
    public string CustomSortString(string order, string s) {
        int[] count = new int[26];
        
        // 统计s中每个字符的出现次数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        StringBuilder result = new StringBuilder();
        
        // 按order中的顺序添加字符
        foreach (char c in order) {
            while (count[c - 'a'] > 0) {
                result.Append(c);
                count[c - 'a']--;
            }
        }
        
        // 添加不在order中的字符
        for (int i = 0; i < 26; i++) {
            while (count[i] > 0) {
                result.Append((char)('a' + i));
                count[i]--;
            }
        }
        
        return result.ToString();
    }
}

var customSortString = function(order, s) {
    const count = new Array(26).fill(0);
    
    // 统计s中每个字符的出现次数
    for (const char of s) {
        count[char.charCodeAt(0) - 97]++;
    }
    
    let result = "";
    
    // 按order中的顺序添加字符
    for (const char of order) {
        const index = char.charCodeAt(0) - 97;
        while (count[index] > 0) {
            result += char;
            count[index]--;
        }
    }
    
    // 添加不在order中的字符
    for (let i = 0; i < 26; i++) {
        while (count[i] > 0) {
            result += String.fromCharCode(97 + i);
            count[i]--;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n + m)
空间复杂度O(1)

其中 n 是字符串 s 的长度，m 是字符串 order 的长度。空间复杂度为 O(1) 是因为我们只使用了固定大小的数组来存储字符计数。

相关题目