java - 按自定义字典顺序对字符串进行排序

Question

使用自定义顺序根据字典顺序对字符串数组进行排序(abcdefghijklmnopqrstuvwxyz 的排列)。这是代码:

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

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

编辑:

Adriana was playing with the English alphabet. When she was done playing with the alphabet, she realised that she had jumbled up the positions of the letters. Now, given a set of words, she wondered what would be the dictionary ordering of these words based on the new alphabet ordering which she made.

In other words, given a permutation of the English alphabet, E and a set of words S, you need to output the lexicographical ordering of the words in the set S based on the new alphabet, E.

Input:

The first line will contain a single integer, T, denoting the number of test cases. T lines follow.

For each test case:

The first line will contain a string, E, the new alphabet ordering, which will be a permutation of abcdefghijklmnopqrstuvwxyz

The next line will contain a single integer M, the size of the set S. S lines follow, each containing a single word, containing lowercase latin characters.

Output: for each test case, output S lines, each line containing one word from the set S, ordered lexicographically.

Constraints

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

Sample Input:

2
abcdefghijklmnopqrstuvwxyz
2
aa
bb
bacdefghijklmnopqrstuvwxyz
2
aa
bb

Sample Output:

aa
bb
bb
aa

Answer 1

这应该适用于任何给定的排列。当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);
    }
}

我想这是某种算法挑战。是吗？ :)