SortMe

Introduction

The problem essentially asks you to sort a list of string based on a new alphabet. The input of the problems gives you the number of strings to be sorted, the new alphabetical order in the form of a string, and the strings that are to be sorted. Problem solved by Paul.

Algorithm

The idea behind the solution is that we can use Java's built in comparator to sort the strings for us. The compare method takes in two strings and returns -1 or 1 based on which string comes first when sorting. The method determines which of the strings shorter length (suppose it has a length L) and iterates through the first L characters in both strings. If any of the first L characters differ, the method will determine the indices of these characters in the alphabet, and will return an int based on which string comes alphabetically first. If none of the first L characters differ, then one string is a prefix of the other, and the method returns an int based on which string is shorter.

Solution - Java

import java.io.*;
import java.util.*;

public class SortMe{
	private static class Comp implements Comparator<String>{
		private String alpha;
		public Comp(String s){
			alpha = s;
		}	
		public int compare(String s1, String s2){
			for(int i = 0;i < Math.min(s1.length(), s2.length());i++){
				if(s1.charAt(i) != s2.charAt(i)){
					return alpha.indexOf(s1.charAt(i)) - alpha.indexOf(s2.charAt(i));
				}
			}
			return s1.length() - s2.length();
		}
	}
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		int year = 1;
		while(true){
			int n = in.nextInt();
			if(n == 0){
				break;
			}
			String[] str = new String[n];
			Comp comp = new Comp(in.next());
			for(int i = 0;i < n;i++){
				str[i] = in.next();
			}
			Arrays.sort(str, comp);
			System.out.println("year "+year++);
			for(String s : str){
				System.out.println(s);
			}
		}
	}
}