题解 | #字符串排序#

题目链接

题目描述

给定一个包含 26 个不同小写字母的字符串，它定义了一种新的字母表顺序。我们需要对 $n$ 个字符串按照这个新顺序进行排序。

排序规则如下：

前缀规则：如果字符串 $s_1$ 是字符串 $s_2$ 的前缀，则 $s_1$ 排在 $s_2$ 前面。
字典序规则：否则，从头开始比较两个字符串，找到第一个不同的字符。这两个字符在给定的新字母表中的顺序，决定了两个字符串的顺序。

解题思路

这是一个自定义排序问题。解决这类问题的标准方法是实现一个自定义的比较函数（或比较器），然后将其传递给语言内置的排序算法（如 C++ 的 std::sort，Java 的 Collections.sort，Python 的 list.sort）。

预处理：建立字符顺序映射

为了能够快速比较任意两个字符在新字母表中的顺序，我们可以先进行一步预处理。

读入定义新字母表顺序的字符串（例如 zyx...a）。
创建一个大小为 26 的数组或哈希表，我们称之为 rank。
遍历这个字母表字符串，rank[c - 'a'] = i 表示字符 c 在新顺序中的排位是 $i$ 。
这样，我们就可以在 $O(1)$ 的时间内查询到任何一个字符的排序优先级。例如，rank['z'-'a'] 为 0，rank['a'-'a'] 为 25。

实现自定义比较函数 `compare(s1, s2)`

这个函数需要判断字符串 s1 是否应该排在 s2 之前。

逐字符比较：
- 使用两个指针，同时从头开始遍历 s1 和 s2，直到其中一个字符串结束。
- 在第 $i$ 个位置，比较 s1[i] 和 s2[i]。
- 获取它们的排名：rank1 = rank[s1[i] - 'a'] 和 rank2 = rank[s2[i] - 'a']。
- 如果 rank1 < rank2，说明 s1 应该排在 s2 前面，比较结束，返回 true。
- 如果 rank1 > rank2，说明 s2 应该排在 s1 前面，比较结束，返回 false。
- 如果 rank1 == rank2，继续比较下一个字符。
处理前缀情况：
- 如果上述循环正常结束，说明一个字符串是另一个的前缀。
- 根据规则 1，较短的字符串（即前缀）应该排在前面。
- 因此，我们只需比较 s1 和 s2 的长度。如果 s1.length() < s2.length()，则 s1 是前缀，应该排在前面。

最终算法步骤

读入自定义字母表，构建 rank 映射。
读入所有 $n$ 个待排序的字符串。
调用标准库的排序函数，并传入我们实现的自定义比较逻辑。
输出排序后的字符串列表。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string order;
    cin >> order;

    vector<int> rank(26);
    for (int i = 0; i < 26; ++i) {
        rank[order[i] - 'a'] = i;
    }

    int n;
    cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; ++i) {
        cin >> strs[i];
    }

    sort(strs.begin(), strs.end(), [&](const string& s1, const string& s2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int min_len = min(len1, len2);

        for (int i = 0; i < min_len; ++i) {
            if (s1[i] != s2[i]) {
                return rank[s1[i] - 'a'] < rank[s2[i] - 'a'];
            }
        }
        return len1 < len2;
    });

    for (const string& s : strs) {
        cout << s << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String order = sc.next();
        int[] rank = new int[26];
        for (int i = 0; i < 26; i++) {
            rank[order.charAt(i) - 'a'] = i;
        }

        int n = sc.nextInt();
        List<String> strs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            strs.add(sc.next());
        }

        Collections.sort(strs, (s1, s2) -> {
            int len1 = s1.length();
            int len2 = s2.length();
            int minLen = Math.min(len1, len2);

            for (int i = 0; i < minLen; i++) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    return Integer.compare(rank[s1.charAt(i) - 'a'], rank[s2.charAt(i) - 'a']);
                }
            }
            return Integer.compare(len1, len2);
        });

        for (String s : strs) {
            System.out.println(s);
        }
    }
}

import sys
import functools

def solve():
    order = sys.stdin.readline().strip()
    rank = {char: i for i, char in enumerate(order)}

    n = int(sys.stdin.readline())
    strs = [sys.stdin.readline().strip() for _ in range(n)]

    def compare(s1, s2):
        len1, len2 = len(s1), len(s2)
        min_len = min(len1, len2)
        
        for i in range(min_len):
            if s1[i] != s2[i]:
                if rank[s1[i]] < rank[s2[i]]:
                    return -1
                else:
                    return 1
        
        if len1 < len2:
            return -1
        elif len1 > len2:
            return 1
        else:
            return 0

    strs.sort(key=functools.cmp_to_key(compare))

    for s in strs:
        print(s)

solve()

算法及复杂度

算法：自定义排序
时间复杂度： $O(N \cdot L \cdot \log N)$ 。其中 $N$ 是字符串的数量， $L$ 是字符串的最大长度。排序算法需要进行 $O(N \log N)$ 次比较，每次比较最多需要 $O(L)$ 的时间。
空间复杂度： $O(N \cdot L)$ 。主要用于存储输入的 $N$ 个字符串。字符排名映射需要 $O(1)$ 的常数空间。