首页 > 试题广场 >

字符串排序

[编程题]字符串排序
  • 热度指数:1533 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定 n 个字符串,请你对这 n 个字符串按照以下规则从小到大排序。

对于任意两个字符串 st ,在排序后应当满足:

- 若 st 的一个前缀,则 s 在排序后的下标小于等于 t 的在排序后的下标。
- 若存在整数 i ,使得 s 的前 i-1 个字符和 t 的前 i-1 个字符相同,且 st 的第 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
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)