精彩的人生

好好工作,好好生活

BlogJava 首页 新随笔 联系 聚合 管理
  147 Posts :: 0 Stories :: 250 Comments :: 0 Trackbacks

声明:代码是作者原创,请勿作商业用途
转载请注明出处

A rare book collector recently discovered a book written in an unfamiliar language that used the same characters as the English language. The book contained a short index, but the ordering of the items in the index was different from what one would expect if the characters were ordered the same way as in the English alphabet. The collector tried to use the index to determine the ordering of characters (i.e., the collating sequence) of the strange alphabet, then gave up with frustration at the tedium of the task.

You are to write a program to complete the collector's work. In particular, your program will take a set of strings that has been sorted according to a particular collating sequence and determine what that sequence is.

Input

The input consists of an ordered list of strings of uppercase letters, one string per line. Each string contains at most 20 characters. The end of the list is signalled by a line dio is the single character `#'. Not all letters are necessarily used, but the list will imply a complete ordering among those letters that are used.

Output

Your output should be a single line containing uppercase letters in the order that specifies the collating sequence used to produce the input data file.

Sample Input

XWY
ZX
ZXY
ZXW
YWWX
#

Sample Output

XZYW


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

public class Problem200 {

    
/**
     * 
@param args
     
*/

    
public static void main(String[] args) {
        ArrayList al 
= new ArrayList();        
        
        
try {
            
while(true){
                BufferedReader cin 
= new BufferedReader( new InputStreamReader( System.in ) );
                String s 
= cin.readLine();
                
if(s==null || s.length()<1)
                    
continue;
                
                
if(s.equals("#"))
                    
break;
                
                
if(s.length()>20){
                    System.out.println(
"length more than 20!");
                    
return;
                }

                
if(!isUpper(s)){
                    System.out.println(
"there are chars not in upper case!");
                    
return;
                }

                al.add(s);
            }

        }
 catch (IOException e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        }

        
        
if(al.size()<1){
            System.out.println(
"NONE");
        }

        
        
char[][] charArr = new char[al.size()][20];
        
for(int i=0; i<al.size(); i++){
            charArr[i] 
= al.get(i).toString().toCharArray();
        }

        
        sort(charArr);
    }


    
private static void sort(char[][] charArr) {
        
char[] result = new char[26];
        
int index = 0;
        
        
char ch;
        
for(int i=0; i<charArr.length; i++){
            
for(int j=0; j<charArr[i].length; j++){
                ch 
= charArr[i][j];
                
if(index==0){
                    result[index] 
= ch;
                    index
++;
                }
else{
                    
if(contains(ch, result, index)){
                        
continue;
                    }
else{
                        result[index] 
= ch;
                        index
++;
                    }

                }

            }

        }

        StringBuffer buffer 
= new StringBuffer();
        
for(int i=0; i<index; i++){
            buffer.append(result[i]);
        }

        
        System.out.println(buffer.toString());
    }


    
private static boolean contains(char ch, char[] result, int index) {
        
boolean flag=false;
        
for(int i=0; i<index; i++){
            
if(result[i]==ch){
                flag
=true;
                
break;
            }

        }

        
return flag;
    }


    
private static boolean isUpper(String s) {
        
boolean result=true;
        
for(int i=0; i<s.length(); i++){
            
if(s.charAt(i)>='A' && s.charAt(i)<='Z')
                
continue;
            
else{
                result
=false;
                
break;
            }

        }

        
return result;
    }


}


欢迎讨论
posted on 2005-12-07 15:20 hopeshared 阅读(571) 评论(3)  编辑  收藏 所属分类: Google Code Jam

Feedback

# re: Rare Order 2006-09-01 06:44 Guest
Have you ever tested your solution?  回复  更多评论
  

# re: Rare Order[未登录] 2007-07-22 00:13 Kelvin
请问它是 怎么排序的,它的顺序是怎么决定的  回复  更多评论
  

# re: Rare Order[未登录] 2014-10-19 04:35 123
@Guest
Wrong at all!!!!  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: