(UVA) Passwords - Solution

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

The solution below is using backtracking. If the current character is a '#', it tries all the words in the dictionary, but if the character is a '0', it tries all the numbers between 0 and 9.


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

class Main {
    public static void rec(String[] words, String rule, int indexRules, StringBuilder sb) {
        if (indexRules == rule.length()) {
            System.out.println(sb.toString());
            return;
        }
       
        if (rule.charAt(indexRules) == '#') {
            for (int j = 0; j < words.length; j++) {
                sb.append(words[j]);
                rec(words, rule, indexRules+1, sb);
                sb.delete(sb.length()-words[j].length(), sb.length());
            }
        }
        else if (rule.charAt(indexRules) == '0') {
            for (int j = 0; j < 10; j++) {
                sb.append(j);
                rec(words, rule, indexRules+1, sb);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        while (sc.hasNext()) {
            int numWords = sc.nextInt();
            String[] words = new String[numWords];
            for (int i = 0; i < numWords; i++) {
                words[i] = sc.next();
            }
           
            int numRules = sc.nextInt();
            String[] rules = new String[numRules];
            for (int i = 0; i < numRules; i++) {
                rules[i] = sc.next();
            }
           
            System.out.println("--");
            for (int j = 0; j < numRules; j++) {
                StringBuilder sb = new StringBuilder();
                rec(words, rules[j], 0, sb);
            }
        }
                                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}