Why wrong answer?


  • 0
    R

    Below is my answer to the problem.
    But with the test case "999" it gives a wrong answer.
    I counted the number of combinations in the correct answer, it is a total of 36 combinations, which seems odd to me since 9 can represent 4 characters, leading to total combinations of 444 = 64 combinations. Is it something that I did not get correctly from the problem?

    public class Solution {
        public List<String> letterCombinations(String digits) {
            HashMap<Character,ArrayList<Character>> map = new HashMap<Character,ArrayList<Character>>();
            ArrayList<Character> l2 = new ArrayList<Character>(Arrays.asList('a', 'b', 'c'));
            ArrayList<Character> l3 = new ArrayList<Character>(Arrays.asList('d', 'e', 'f'));
            ArrayList<Character> l4 = new ArrayList<Character>(Arrays.asList('g', 'h', 'i'));
            ArrayList<Character> l5 = new ArrayList<Character>(Arrays.asList('j', 'k', 'l'));
            ArrayList<Character> l6 = new ArrayList<Character>(Arrays.asList('m', 'n', 'o'));
            ArrayList<Character> l7 = new ArrayList<Character>(Arrays.asList('p', 'q', 'r', 's'));
            ArrayList<Character> l8 = new ArrayList<Character>(Arrays.asList('t', 'u', 'v'));
            ArrayList<Character> l9 = new ArrayList<Character>(Arrays.asList('w', 'x', 'y', 'z'));
            map.put('2',l2);
            map.put('3',l3);
            map.put('4',l4);
            map.put('5',l5);
            map.put('6',l6);
            map.put('7',l7);
            map.put('8',l8);
            map.put('9',l9);
            
            List<String> result = new ArrayList<String>();
            if(digits.length()==0){
                result.add("");
                return result;
            }
            
            String start = "";
            fill(start,map,0,digits,result);
            
            return result;
            
        }
        
        public void fill(String start, HashMap<Character,ArrayList<Character>> map, int index, String digits, List<String> result){
            char c = digits.charAt(index);
            if(map.get(c).size()==4){
                StringBuilder sb1 = new StringBuilder(start);
            StringBuilder sb2 = new StringBuilder(start);
            StringBuilder sb3 = new StringBuilder(start);
            StringBuilder sb4 = new StringBuilder(start);
            
            String s1 = sb1.append(map.get(c).get(0)).toString();
            String s2 = sb2.append(map.get(c).get(1)).toString();
            String s3 = sb3.append(map.get(c).get(2)).toString();
            String s4 = sb4.append(map.get(c).get(3)).toString();
            
            if(index == digits.length()-1){
                if(!result.contains(s1))
                result.add(s1);
                if(!result.contains(s2))
                result.add(s2);
                if(!result.contains(s3))
                result.add(s3);
                if(!result.contains(s4))
                result.add(s4);
            } else {
                fill(s1,map,index+1,digits,result);
                fill(s2,map,index+1,digits,result);
                fill(s4,map,index+1,digits,result);
            }
            } else {
            StringBuilder sb1 = new StringBuilder(start);
            StringBuilder sb2 = new StringBuilder(start);
            StringBuilder sb3 = new StringBuilder(start);
            
            String s1 = sb1.append(map.get(c).get(0)).toString();
            String s2 = sb2.append(map.get(c).get(1)).toString();
            String s3 = sb3.append(map.get(c).get(2)).toString();
            
            if(index == digits.length()-1){
                if(!result.contains(s1))
                result.add(s1);
                if(!result.contains(s2))
                result.add(s2);
                if(!result.contains(s3))
                result.add(s3);
    
            } else {
                fill(s1,map,index+1,digits,result);
                fill(s2,map,index+1,digits,result);
                fill(s3,map,index+1,digits,result);
    
            }
            }
        }
    }

  • 0
    S

    Can you post the expected answer, your answer, as well as their difference here?


  • 0
    R

    Sorry, it seems that I misread the OJ result, it is my answer that outputs only 36 results. Being too tired really is not good for solving problems. :(


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.