首页 > 试题广场 >

字符串排序

[编程题]字符串排序

热度指数：36 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定 $n$ 个字符串，请你对这 $n$ 个字符串按照以下规则从小到大排序。

对于任意两个字符串 $s$ 和 $t$ ，在排序后应当满足：

- 若 $s$ 是 $t$ 的一个前缀，则 $s$ 在排序后的下标小于等于 $t$ 的在排序后的下标。
- 若存在整数 $i$ ，使得 $s$ 的前 $i-1$ 个字符和 $t$ 的前 $i-1$ 个字符相同，且 $s$ 和 $t$ 的第 $i$ 个字符不同，则比较第 $i$ 个字符的大小关系（字符的大小关系顺序由输入数据给出）。若 $s$ 的第 $i$ 个字符小于等于 $t$ 的第 $i$ 个字符，则 $s$ 在排序后的下标小于等于 $t$ 的在排序后的下标。

容易发现，上述排序方法的排序结果是唯一的。

输入描述:

第一行输入一个字符串，包含  个互不相同的小写字母。记  表示字母  是该字符串的第  个字符，则字母  小于等于字母  当且仅当  。

第二行输入一个整数  ，表示待排序字符串的数量。

接下来  行，每行一个仅包含小写字母的字符串  ，表示一个待排序的字符串。

输出描述:

按照排序后字符串位置下标从小到大的顺序输出  行，每行一个字符串，表示排序的结果。

示例1

输入

abcdefghijklmnopqrstuvwxyz
3
aaa
aac
aaaa

输出

aaa
aaaa
aac

示例2

输入

zyxwvutsrqponmlkjihgfedcba
3
aaa
aac
aaaa

输出

aac
aaa
aaaa

算法知识视频讲解

一笑而过2222

题目：字符串排序给定 n 个字符串，需按以下规则从小到大排序： - 若 s 是 t 的一个前缀，则 s 在排序后的下标小于等于 t 的排序后下标。 - 若存在整数 i，使得 s 的前 i - 1 个字符和 t 的前 i - 1 个字符相同，且 s 和 t 的第 i 个字符不同，那么比较第 i 个字符的大小关系（字符大小关系由输入的含26个不同小写字母的字符串确定）。若 s 的第 i 个字符小于 t 的第 i 个字符，则 s 在排序后的下标小于等于 t 的排序后下标。限制条件 - 时间限制：C/C++ 1秒，其他语言2秒 - 空间限制：C/C++ 256M，其他语言512M 输入描述 - 第一行：一个包含26个互不相同小写字母的字符串，用于确定字母大小关系，记 rank(c) 表示字母 c 是该字符串的第 rank(c) 个字符，字母 a 小于等于字母 b 当且仅当 rank(a) \leq rank(b)。 - 第二行：整数 n（1 \leq n \leq 1000），表示待排序字符串的数量。 - 接下来 n 行：每行一个仅包含小写字母的字符串 s_i（|s_i| \leq 1000），为待排序的字符串。输出描述按照排序后字符串位置下标从小到大的顺序输出 n 行，每行一个字符串，表示排序结果。示例 - 示例1 - 输入： - abcdefghijklmnopqrstuvwxyz - 3 - aaa - aac - aaaa - 输出： - aaa - aaaa - aac - 示例2 - 输入： - zyxwvutsrqponmlkjihgfedcba - 3 - aaa - aac - aaaa - 输出： - aac - aaa - aaaa

发表于 2025-06-18 11:37:41 回复(2)