按自定义词典顺序排序字符串

Question

根据字典顺序和自定义顺序对字符串数组进行排序（一种排列形式）。这是代码：

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author sabertooth
 */
public class SortString {
    /**
     * @param args the command line arguments
     */
    private static char[] index;
    private static BufferedReader br;

    public static void main(String[] args) throws Exception {
        // TODO code application logic here
        br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());

        for (int i = 0; i < testCases; i++) {
            String dictionary = br.readLine();

            index = new char[dictionary.length()];
            index = dictionary.toCharArray();

            int set = Integer.parseInt(br.readLine());

            String[] unsortedInput = new String[set];
            String[] sortedInput = new String[set];
            for (int j = 0; j < set; j++) {
                unsortedInput[j] = br.readLine();
            }

            if (unsortedInput.length <= 1) {
                System.out.println(unsortedInput[0]);
            } else {
                // merge sort on this array
                sortedInput = mergeSort(unsortedInput);
                for (int k = 0; k < sortedInput.length; k++) {
                    System.out.println(sortedInput[k]);
                }
            }
        }
    }

    private static String[] mergeSort(String[] unsortedInput) {
        if (unsortedInput.length <= 1) {
            return unsortedInput;
        }

        String[] left;
        String[] right;
        int middle = unsortedInput.length / 2;
        if (unsortedInput.length % 2 == 0) {
            left = new String[middle];
            right = new String[middle];
        } else {
            left = new String[middle];
            right = new String[middle + 1];
        }
        System.arraycopy(unsortedInput, 0, left, 0, middle);
        System.arraycopy(unsortedInput, middle, right, 0, unsortedInput.length - middle);

        left = mergeSort(left);
        right = mergeSort(right);
        return merge(left, right);
    }

    private static String[] merge(String[] left, String[] right){
        List<String> leftList = new ArrayList<String>();
        List<String> rightList = new ArrayList<String>();
        List<String> result = new ArrayList<String>();

        leftList.addAll(Arrays.asList(left));
        rightList.addAll(Arrays.asList(right));

        while (leftList.size() > 0 || rightList.size() > 0) {
             if (leftList.size() > 0 && rightList.size() > 0) {
                // my own comparison
                if (compare(leftList.get(0), rightList.get(0)) == -1) {
                    // leftString is less than right string
                    result.add(leftList.get(0));
                    leftList = leftList.subList(1, leftList.size());
                } else
                if (compare(leftList.get(0), rightList.get(0)) == 1) {
                    //left string is greater than right string
                    result.add(rightList.get(0));
                    rightList = rightList.subList(1, rightList.size());
                } else
                if (compare(leftList.get(0), rightList.get(0)) == 0) {
                    // leftString is equal to right string
                    result.add(leftList.get(0));
                    leftList = leftList.subList(1, leftList.size());
                }
            } else
            if (leftList.size() > 0) {
                for (int i = 0; i < leftList.size(); i++) {
                    result.add(leftList.get(i));
                }
                leftList.clear();
            } else
            if (rightList.size() > 0) {
                for (int i = 0; i < rightList.size(); i++) {
                    result.add(rightList.get(i));
                }
                rightList.clear();
            }
        }
        String[] sortedInput = new String[result.size()];
        for (int i = 0; i < result.size(); i++) {
            sortedInput[i] = result.get(i);
        }
        return sortedInput;
    }

    private static int compare(String leftString, String rightString) {
        // return -1 if left string is less than right string else left string is greater than right string return 1

        int min = Math.min(leftString.length(), rightString.length());
        int response = 0;
        for (int i = 0; i < min; i++) {
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == -1) {
                response = -1;
                break;
            } else
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 1) {
                response = 1;
                break;
            } else
            if (compareChar(leftString.charAt(i), rightString.charAt(i)) == 0) {
                response = 0;

            }
        }
        return response;
    }

    private static int compareChar(char x, char y) {
        // returns true if x < y
        int indexofx = 0;
        int indexofy = 0;
        int response = 0;
        for (int i = 0; i < index.length; i++) {
            if (index[i] == x) {
                indexofx = i;
            }
            if (index[i] == y) {
                indexofy = i;
            }
        }
        if (indexofx < indexofy) {
            response = -1;
        } else
        if (indexofx > indexofy) {
            response = 1;
        } else
        if (indexofx == indexofy) {
            response = 0;
        }
        return response;
    }
}

问题是，当我对一些输入运行此命令时，输出是正确的，而对于其他输入，输出是不正确的。我一直在调试它，但没有找到错误。

编辑：

阿德里安娜正在玩英文字母表。当她玩完字母表后，她意识到她把字母的位置弄乱了。现在，给定一组单词，她想知道根据她制作的新字母表排序，这些单词的字典排序是什么。

换句话说，给定英语字母表E和一组单词S的排列，您需要根据新的字母表E输出集合S中单词的词典顺序。

输入：

第一行将包含一个整数T，表示测试用例的数量。T行紧随其后。

对于每个测试用例：

第一行将包含一个字符串E，即新的字母顺序，它将是一个排列

下一行将包含一个整数M，后面是一组大小为S的行，每个行包含一个单词，包含小写拉丁字符。

输出：对于每个测试用例，输出S行，每行包含集合S中的一个单词，按字典顺序排列。

约束条件

1 <= T <= 1000 
1 <= M <= 100 
1 <= |W| <= 50

示例输入：

2
abcdefghijklmnopqrstuvwxyz
2
aa
bb
bacdefghijklmnopqrstuvwxyz
2
aa
bb

样本输出：

aa
bb
bb
aa

Answer 1

字符串比较函数不正确：您只比较最短的长度，为A和AB返回0。当一个字符串是另一个字符串的前缀时，您应该比较长度。

字符比较函数不必要地复杂，并且认为索引之外的所有字符都与索引中的第一个字母相同。您只能根据索引对小写字母重新排序。

    private static int compare(String leftString, String rightString) {
        // return -1 if left string is less than right string else left string is greater than right string return 1

        int len1 = leftString.length();
        int len2 = rightString.length();
        int min = Math.min(len1, len2);
        for (int i = 0; i < min; i++) {
            int cmp = compareChar(leftString.charAt(i), rightString.charAt(i));
            if (cmp != 0) {
                return cmp;
            }
        }
        return len1 == len2 ? 0 : (len1 < len2 ? -1 : 1);
    }

    /* lexicographical comparison with custom order for lowercase letters */
    private static int compareChar(char x, char y) {
        if (x == y)
            return 0;
        int indexofx = index.indexOf(x);
        int indexofy = index.indexOf(y);
        if (indexofx >= 0) {
            x = 'a' + indexofx;
        }
        if (indexofy >= 0) {
            y = 'a' + indexofy;
        }
        // if index is a permutation of the lowercase letters,
        // we can assume x != y 
        return x < y ? -1 : 1;
    }
}

Answer 2

这应该适用于任何给定的排列。当java为您提供内置排序时，为什么要使用自定义排序函数（除非您必须对自定义类对象进行排序）？

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;

class TestClass {
    public static ArrayList<String> res;
    static void sort(String dictionary, String[] words, int count){
        String eng = "abcdefghijklmnopqrstuvwxyz";
        String[] tempArray = new String[count];
        String temp="";
        char ch;
        int index, m=0;
        for(String x : words){
            temp = "";
            for(int l =0 ;l<x.length(); l++){
                ch = x.charAt(l);
                index = dictionary.indexOf(ch);
                temp = temp + eng.charAt(index);
            }
            tempArray[m] = temp;
            m++;
        }

        Arrays.sort(tempArray);
        for(String x : tempArray){
            temp = "";
            for(int l =0 ;l<x.length(); l++){
                ch = x.charAt(l);
                index = eng.indexOf(ch);
                temp = temp + dictionary.charAt(index);
            }
            res.add(temp);

        }
    }
    public static void main(String args[] ) throws Exception {
        res = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int count;
        String [] words;
        String dictionary;
        for (int i = 0; i < N; i++) {
            dictionary = br.readLine();
            count = Integer.parseInt(br.readLine());
            words = new String[count];
            for(int j =0; j<count; j++){
                words[j] = br.readLine();
            }
            sort(dictionary,words,count);
        }
        for(String x : res)
        System.out.println(x);
    }
}

我想这是某种算法挑战。是吗？：）