(UVA) Generating Fast - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1039

The solution below used Backtracking to find all the permutation possible.


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

class Main {
    public int[] considered;
    public String line;
    public TreeSet<String> strings; // keep string sorted lexicographically
    
    public void rec(StringBuilder sb) {
        if (sb.length() == line.length()) {
            strings.add(sb.toString());
            return;
        }
        
        for (int i = 0; i < line.length(); i++) {
            if (considered[i] == 1) {
                continue;
            }
            considered[i] = 1;
            sb.append(line.charAt(i));
            rec(sb);
            sb.deleteCharAt(sb.length()-1);
            considered[i] = 0;
        }
    }
    
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        line = br.readLine();
        int numTests = Integer.parseInt(line);
        for (int i = 0; i < numTests; i++) {
            line = br.readLine();
            
            considered = new int[line.length()];
            strings = new TreeSet<>();
            StringBuilder sb = new StringBuilder();
            rec(sb);
            
            Iterator it = strings.iterator();
            while (it.hasNext()) {
                System.out.println(it.next());
            }
            System.out.println();
        }            
                       
        return;
    }
    
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
        
        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução