Listing all possible names from a phone number

Question

In the program we have to input a number and then calculate all the possible name we can form according to the following rule:

2: A,B,C     5: J,K,L    8: T,U,V
3: D,E,F     6: M,N,O    9: W,X,Y
4: G,H,I     7: P,R,S

Just like we did on a keypad phone. Q and Z have been excluded (for simplicity, I believe)

For example 4734 produces

GPDG GPDH GPDI GPEG GPEH GPEI GPFG GPFH GPFI GRDG GRDH GRDI
GREG GREH GREI GRFG GRFH GRFI GSDG GSDH GSDI GSEG GSEH GSEI
GSFG GSFH GSFI HPDG HPDH HPDI HPEG HPEH HPEI HPFG HPFH HPFI
HRDG HRDH HRDI HREG HREH HREI HRFG HRFH HRFI HSDG HSDH HSDI
HSEG HSEH HSEI HSFG HSFH HSFI IPDG IPDH IPDI IPEG IPEH IPEI
IPFG IPFH IPFI IRDG IRDH IRDI IREG IREH IREI IRFG IRFH IRFI
ISDG ISDH ISDI ISEG ISEH ISEI ISFG ISFH ISFI

The digits in the inputted number can vary from 1 through 12.

I tried to do this using recursion.

import java.util.*;
import java.io.*;
public class namenum{
        public static void main(String[] args) throws Exception{

        Scanner sc = new Scanner(new File("namenum.in"));

        PrintWriter pw  = new PrintWriter(new File("namenum.out"));
        String n = sc.next();
        ArrayList<String> ans = new ArrayList<>();
        List<Character> arr2 = new ArrayList<>();
        arr2.add('A');
        arr2.add('B');
        arr2.add('C');

        List<Character> arr3 = new ArrayList<>();
                arr3.add('D');
        arr3.add('E');
        arr3.add('F');

        List<Character> arr4 = new ArrayList<>();
        arr4.add('G');
        arr4.add('H');
        arr4.add('I');

        List<Character> arr5 = new ArrayList<>();
        arr5.add('J');
        arr5.add('K');
        arr5.add('L');

        List<Character> arr6 = new ArrayList<>();
        arr6.add('M');
        arr6.add('N');
        arr6.add('O');
        List<Character> arr7 = new ArrayList<>();
        arr7.add('P');
        arr7.add('Q');
        arr7.add('R');


        List<Character> arr8 = new ArrayList<>();
        arr8.add('T');
        arr8.add('U');
        arr8.add('V');

        List<Character> arr9 = new ArrayList<>();
        arr9.add('W');
        arr9.add('X');
        arr9.add('Y');

        List<List<Character>> Lists = new ArrayList<>();
        Lists.add(arr2);
        Lists.add(arr3);
        Lists.add(arr4);
        Lists.add(arr5);
        Lists.add(arr6);
        Lists.add(arr7);
        Lists.add(arr8);
        Lists.add(arr9);

        List<String> result = new ArrayList<String>();
        genPermutations(Lists, result, 0, "");
        boolean ansFound = false;
        for(int i = 0; i< result.size(); i++){
            String name = result.get(i);
            if(isInDict(name)){
                pw.println(name);
                ansFound = true;
            }

        }
        if (!ansFound){
            pw.println("NONE");
        }
        pw.close();


    }
    static boolean isInDict(String name) throws Exception{
        boolean ans = false;
        Scanner dict = new Scanner(new File("dict.txt"));
        while(dict.hasNext()){
            if(dict.next() == name){
                ans = true;
                break;
            }
        }
        return ans;

    }

    static void genPermutations(List<List<Character>> Lists, List<String> result, int depth, String current){
        if(depth == Lists.size()){
            result.add(current);
            return ;
        }
        for(int i = 0; i<Lists.get(depth).size();i++){
            genPermutations(Lists, result, depth+1,current+Lists.get(depth).get(i));
        }
    }
    }

But it uses more time (2.128 seconds to be precise) than the accepted 1 second and I get a time limit exceeded verdict.

The question can be found here USACO

What are the ways in which I can simplify the program?

Answer 1

Without the link, I can only make certain assumptions, so I am going to give a couple of global comments:

• When checking if something is contained in a dictionary, you each time read the file again. Second, you can linearly through it in order to determine if a name is contained in it or not. This is very, very slow. Is this because you have some memory constraints? Because else, it would be much faster to read it at the start, and use a HashSet to check for existence.

• Should you be able to read the whole file in memory, perhaps you could even create a mapping between the names and the key combinations that make up this name, by precalculating this. I think that would be a rather optimal solution?

• genPermutations does not work. You pass a depth, which is basically a key index, and generate all permutations from that key until the final key. If you nevertheless keep and fix the genPermutations method, you have another point which can be improved. As I commented earlier, if you would look at the generated results, you could notice a lot of duplication. Take your 4734 example, which among other things generates GPDG, HPDGand IPDG. The three strings are equal except for the first letter. This means you are calculating a lot of the same things. This could be cached.

Some minor remarks:

• Class names should be uppercase (or better, CamelCase), e.g. NameNum

• Variables should start with a lowercase, so List<List<Character>> lists = new ArrayList<>();

• Do not use reference equality with Strings, instead use the equals method. You might get unexpected results otherwise.