[编程题]字符串排序

字符串排序

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

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

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

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

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 256M，其他语言512M

输入描述：

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

第二行输入一个整数 n [1, 1000] ，表示待排序字符串的数量。

接下来 n 行，每行一个仅包含小写字母的字符串 si (|si| <= 1000)  ，表示一个待排序的字符串。

输出描述：

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

示例1

输入例子：

abcdefghijklmnopqrstuvwxyz
3
aaa
aac
aaaa

输出例子：

aaa
aaaa
aac

示例2

输入例子：

zyxwvutsrqponmlkjihgfedcba
3
aaa
aac
aaaa

输出例子：

aac
aaa
aaaa

代码如下：

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);
        // }
    }
}