首页 > 试题广场 >

字符串排序

[编程题]字符串排序
  • 热度指数：1533 时间限制：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 的在排序后的下标。

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

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

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

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


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

输入

abcdefghijklmnopqrstuvwxyz
3
aaa
aac
aaaa

输出

aaa
aaaa
aac
示例2

输入

zyxwvutsrqponmlkjihgfedcba
3
aaa
aac
aaaa

输出

aac
aaa
aaaa
算法知识视频讲解
查看答案及解析
添加回答
Python
牛客673176706号头像 牛客673176706号 
strlist = input().strip()
dic = {}
for i, c in enumerate(strlist):
    dic[c] = i + 1
n = int(input().strip())
strings = []
for _ in range(n):
    strings.append(input().strip())
strings.sort(key=lambda s: [dic.get(c, 0) for c in s])

for s in strings:
    print(s)


编辑于 2025-10-11 09:54:40 回复(0)
希望奇迹发生的小黄鸭很不想泡池子头像 希望奇迹发生的小黄鸭很不想泡池子 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        String letters = in.next();
        char[] lettersArray = letters.toCharArray();
        int[] letterWeight = new int[1024];
        for(int j = 0; j < lettersArray.length; j++) {
            int charValue = lettersArray[j];
            letterWeight[charValue] = j;
        }

        int n = in.nextInt();
        int i = 0;
        String[] strArray = new String[n];
        while(i < n) {
            strArray[i] = in.next();
            i++;
        }

        Arrays.sort(strArray, new Comparator<String>() {
            public int compare(String a, String b) {
                int ret = 0;
                int len = Math.min(a.length(), b.length());
                for (int i = 0; i < len; i++) {
                    int v1 = letterWeight[a.charAt(i)];
                    int v2 = letterWeight[b.charAt(i)];

                    ret = v1 - v2;
                    if (ret != 0) {
                        return ret;
                    }
                }

                
                return a.length() - b.length();
            }
        });

        for (String item : strArray) {
            System.out.println(item);
        }

        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
    }
}

发表于 2025-06-25 19:48:35 回复(0)
JavaScript
枯木逢春只醉看头像 枯木逢春只醉看
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let sortMap = new Map(),n,list=[],count=0
    while(line = await readline()){
        if(count==0){
            let step=1
            for(let i of line){
                sortMap.set(i,step)
                step++
            }
            count++
        }else if(count ==1){
            n = parseInt(line)
            count++
        }else{
            list.push(line)
        }
    }
    list.sort((a,b)=>{
        let length = Math.max(a.length,b.length)
        for(let i=0;i<length;i++){
            if(!a[i]) return -1
            if(!b[i]) return 1
            if(a[i]!=b[i]){
                return  sortMap.get(a[i]) - sortMap.get(b[i])
            }
        }
    })
    for(let i of list) console.log(i)
}()

发表于 2025-12-09 14:41:23 回复(0)
谁把工作偷走了头像 谁把工作偷走了 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 构建等级表
        String str = sc.next();
        Map<Character,Integer> rank = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            rank.put(str.charAt(i),i);
        }
        // 添加需排序的字符串
        int num = sc.nextInt();
        List<String> list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            list.add(sc.next());
        }
        // 进行排序
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                int len1 = s1.length();
                int len2 = s2.length();
                int minLen = Math.min(len1, len2);

                // 比较每个字符
                for (int i = 0; i < minLen; i++) {
                    char c1 = s1.charAt(i);
                    char c2 = s2.charAt(i);
                    int rank1 = rank.get(c1);
                    int rank2 = rank.get(c2);

                    if (rank1 != rank2) {
                        return rank1 - rank2;
                    }
                }

                // 如果前面的字符都相同，则长度短的在前
                return len1 - len2;
            }
        });

        // 输出结果
        for (String s : list) {
            System.out.println(s);
        }
    }
}

发表于 2025-10-27 22:47:08 回复(0)
一笑而过2222头像 一笑而过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)
提交观点

问题信息

字符串 京东 排序
难度：
5条回答 660浏览

热门推荐

相关试题

字符串排序

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号