Wednesday, April 30, 2014

Permutations for digits represented by Phone Number

This is a stackoverflow question: http://stackoverflow.com/questions/1851239/permutations-for-digits-represented-by-phone-number

This can be done by dynamic programming and just need to keep track of the previous result list and build result based on it.


public static List<String> allWordsFromPhonePad(int number){
HashMap<Integer, String > h = new HashMap<Integer, String>(){{
        put(1,"");
        put(2, "ABC");
        put(3, "DEF");
        put(4, "GHI");
        put(5, "JKL");
        put(6, "MNO");
        put(7, "PQRS");
        put(8, "TUV");
        put(9, "WXYZ");
        put(0, "");
    }};
    List<String> result = new ArrayList<String>();
    result.add("");
    while(number>0){
    int last = number%10;
    List<String> temp = new ArrayList<String>();
   
    for(String s: result){
    String map = h.get(last);
    for(char c : map.toCharArray()){
    temp.add(String.valueOf(c) + s);
    }
    }    
    number = (number-last)/10;
    if(!temp.isEmpty())
    result = temp;
    }
   
    return result;
}

No comments:

Post a Comment