Pages

Sunday 9 September 2012

UVA - 195-Anagram

import java.io.*;
import java.util.Arrays;
import java.util.IllegalFormatException;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.swing.JFileChooser;
import javax.swing.JOptionPane;

public class Main {

    public static void main(String[] args) throws FileNotFoundException, IOException {
        TextIO.readStream(System.in);
        int cases = TextIO.getlnInt();
        for(int j=0;j<cases;j++){
            String m =TextIO.getlnString();
            Letter l[] = new Letter[m.length()];
            for (int i = 0; i < m.length(); i++) {
                l[i] = new Letter();
                l[i].setX(m.charAt(i));
            }
            Arrays.sort(l);
            char []n=new char[m.length()];
            for (int i = 0; i < m.length(); i++) {
                n[i]=l[i].getX();
            }
            m= new String(n);
            permutationsChar(0, m, new boolean[m.length()], new char[m.length()]);
        }
    }

    public static void permutationsChar(int i, String s, boolean[] v, char[] res) {
        if (i == res.length) {
            System.out.println(new String(res));
        } else {
            for (int j = 0; j < s.length(); j++) {
                if (!v[j]) {
                    /* this extra check avoids repetetion in permutations */
                    /* when the given string contains repeated characters */
                    /*for this check to work the string s must be sorted somehow*/
                    if ((j > 0 && !v[j - 1] && s.charAt(j - 1) == s.charAt(j))) {
                        continue;
                    }
                    v[j] = true;// choose current character and mark it as
                    // visited
                    res[i] = s.charAt(j);// write it into the permutation array
                    permutationsChar(i + 1, s, v, res);// recurse to choose next
                    // character
                    v[j] = false;// back track
                    res[i] = '-';
                }
            }
        }
    }
}

class Letter implements Comparable<Letter> {

    char x;
    Boolean UP;

    public Boolean getUP() {
        return UP;
    }

    public void setUP(Boolean UP) {
        this.UP = UP;
    }

    public char getX() {
        return x;
    }

    public void setX(char x) {
        this.x = x;
    }

    @Override
    public int compareTo(Letter m) {
        if (m.getX() == this.getX()) {
            return 0;
        }
        if (m.getX() >96 && this.getX() >96 ) {
            if (m.getX() > this.getX()) {
                return -1;
            } else {
                return 1;
            }
        } else if (m.getX() >96  && this.getX() >64 ) {
            if (m.getX() - 32 > this.getX()) {
                return -1;
            }else if(m.getX()-32==this.getX()){
                return -1;
            }else {
                return 1;
            }
        } else if (m.getX() > 64 && this.getX() > 96) {
            if (m.getX()  > this.getX()- 32) {
                return -1;
            }else {
                return 1;
            }
        }
        if (m.x > this.getX()) {
            return -1;
        } else {
            return 1;
        }
    }
}

No comments:

Post a Comment