字符串排序

[牛客链接](https://www.nowcoder.com/practice/9ad2f07d6eb74a6e935e54279b29910d)

思路

本题要求按自定义字母顺序对字符串进行字典序排序。

输入的第一行是一个包含 26 个不同小写字母的字符串，它定义了字母的大小关系：排在前面的字母"更小"。例如 zyxwvutsrqponmlkjihgfedcba 表示 z 最小、a 最大。

排序规则和标准字典序完全一致，只是字母的大小关系由输入决定：

逐字符比较，遇到不同字符时，按自定义顺序判断大小。
若一个字符串是另一个的前缀，则较短的排在前面。

做法： 用一个数组 rank[c] 记录每个字母 c 在自定义顺序中的位置（越小排越前），然后在比较函数中用 rank 值替代原始字符值即可。排序直接使用语言自带的排序函数。

以样例 2 为例：

自定义顺序 zyxwvutsrqponmlkjihgfedcba，其中 c 的位置是 23，a 的位置是 25。比较 aac 和 aaa：前两个字符相同，第三个字符 c（rank 23）< a（rank 25），所以 aac 排在 aaa 前面。aaaa 以 aaa 为前缀且更长，排在 aaa 后面。最终结果：aac, aaa, aaaa。

复杂度

时间复杂度： $O(n \cdot L \cdot \log n)$ ，其中 $n$ 是字符串数量， $L$ 是字符串平均长度。排序 $O(n \log n)$ 次比较，每次比较 $O(L)$ 。
空间复杂度： $O(n \cdot L)$ ，存储所有字符串。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string order;
    cin >> order;

    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& a, const string& b) {
        int len = min(a.size(), b.size());
        for (int i = 0; i < len; i++) {
            if (a[i] != b[i]) {
                return rank[a[i] - 'a'] < rank[b[i] - 'a'];
            }
        }
        return a.size() < b.size();
    });

    for (int i = 0; i < n; i++) {
        cout << strs[i] << '\n';
    }

    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String order = br.readLine().trim();

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

        int n = Integer.parseInt(br.readLine().trim());
        String[] strs = new String[n];
        for (int i = 0; i < n; i++) {
            strs[i] = br.readLine().trim();
        }

        Arrays.sort(strs, (a, b) -> {
            int len = Math.min(a.length(), b.length());
            for (int i = 0; i < len; i++) {
                if (a.charAt(i) != b.charAt(i)) {
                    return rank[a.charAt(i) - 'a'] - rank[b.charAt(i) - 'a'];
                }
            }
            return a.length() - b.length();
        });

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(strs[i]).append('\n');
        }
        System.out.print(sb);
    }
}