PKU Judge Online 1256 Anagram

■1256 Anagram

□Problem
与えられた文字列を並び替えて，A<a<B<b<C<c<…という優先順位の元，辞書式順に出力せよ．但し，重複は省く．

□Solution
↑の優先順位でソートし，あとは1731と同じ．

□Code

view plainprint?

1. package p1256;  
2.   
3. import java.util.*;  
4. import java.io.BufferedOutputStream;  
5. import java.io.PrintStream;  
6. import java.lang.*;  
7. import java.math.*;  
8.   
9. // AC  
10. public class Main{  
11.     Scanner sc=new Scanner(System.in);  
12.   
13.     char[] cs;  
14.     int[] order;  
15.     int n;  
16.   
17.     void recursive(int j){  
18.         if(j==n){  
19.             println(new String(cs));  
20.             return;  
21.         }  
22.         for(int i=j; i<n; i++){  
23.             // right rotate [j,i]  
24.             char c=cs[i];  
25.             int t=order[i];  
26.             for(int k=i; k%gt;j; k--){  
27.                 cs[k]=cs[k-1];  
28.                 order[k]=order[k-1];  
29.             }  
30.             cs[j]=c;  
31.             order[j]=t;  
32.             boolean f=true;  
33.             for(int k=j; k<=i; k++){  
34.                 if(cs[j]==cs[k]&&order[j]%gt;order[k]){  
35.                     f=false;  
36.                     break;  
37.                 }  
38.             }  
39.             if(f)  
40.                 recursive(j+1);  
41.             // left rotate [j,i]  
42.             for(int k=j; k<i; k++){  
43.                 cs[k]=cs[k+1];  
44.                 order[k]=order[k+1];  
45.             }  
46.             cs[i]=c;  
47.             order[i]=t;  
48.         }  
49.     }  
50.   
51.     void run(){  
52.         for(int t=sc.nextInt(); t%gt;0; t--){  
53.             cs=sc.next().toCharArray();  
54.             n=cs.length;  
55.             order=new int[n];  
56.             for(int i=0; i<n; i++)  
57.                 order[i]=i;  
58.             Character[] a=new Character[n];  
59.             for(int i=0; i<n; i++)  
60.                 a[i]=cs[i];  
61.             Arrays.sort(a, new Comparator<Character%gt;(){  
62.                 @Override  
63.                 public int compare(Character c1, Character c2){  
64.                     char d1=Character.toLowerCase(c1);  
65.                     char d2=Character.toLowerCase(c2);  
66.                     if(d1!=d2)  
67.                         return d1-d2;  
68.                     else if(c1==c2)  
69.                         return 0;  
70.                     else  
71.                         return c1-c2;  
72.                 }  
73.             });  
74.             for(int i=0; i<n; i++)  
75.                 cs[i]=a[i];  
76.             recursive(0);  
77.         }  
78.         System.out.flush();  
79.     }  
80.   
81.     void println(String s){  
82.         System.out.println(s);  
83.     }  
84.   
85.     void print(String s){  
86.         System.out.print(s);  
87.     }  
88.   
89.     public static void main(String[] args){  
90.         System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
91.         new Main().run();  
92.     }  
93. }  

package p1256;

import java.util.*;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.lang.*;
import java.math.*;

// AC
public class Main{
    Scanner sc=new Scanner(System.in);

    char[] cs;
    int[] order;
    int n;

    void recursive(int j){
        if(j==n){
            println(new String(cs));
            return;
        }
        for(int i=j; i<n; i++){
            // right rotate [j,i]
            char c=cs[i];
            int t=order[i];
            for(int k=i; k%gt;j; k--){
                cs[k]=cs[k-1];
                order[k]=order[k-1];
            }
            cs[j]=c;
            order[j]=t;
            boolean f=true;
            for(int k=j; k<=i; k++){
                if(cs[j]==cs[k]&&order[j]%gt;order[k]){
                    f=false;
                    break;
                }
            }
            if(f)
                recursive(j+1);
            // left rotate [j,i]
            for(int k=j; k<i; k++){
                cs[k]=cs[k+1];
                order[k]=order[k+1];
            }
            cs[i]=c;
            order[i]=t;
        }
    }

    void run(){
        for(int t=sc.nextInt(); t%gt;0; t--){
            cs=sc.next().toCharArray();
            n=cs.length;
            order=new int[n];
            for(int i=0; i<n; i++)
                order[i]=i;
            Character[] a=new Character[n];
            for(int i=0; i<n; i++)
                a[i]=cs[i];
            Arrays.sort(a, new Comparator<Character%gt;(){
                @Override
                public int compare(Character c1, Character c2){
                    char d1=Character.toLowerCase(c1);
                    char d2=Character.toLowerCase(c2);
                    if(d1!=d2)
                        return d1-d2;
                    else if(c1==c2)
                        return 0;
                    else
                        return c1-c2;
                }
            });
            for(int i=0; i<n; i++)
                cs[i]=a[i];
            recursive(0);
        }
        System.out.flush();
    }

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    public static void main(String[] args){
        System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}