O(n*k) solution for letter combination of phone numbers, where n is number of digit and k is total number of possible combinations


  • 0
    P

    O(n*k) solution for letter combination of phone numbers, where n is number of digit and k is total number of possible combinations

     public List<String> letterCombinations(String digits) {
    		List<String> strings = new LinkedList<>();
    		if (digits == null || digits.equals(""))
    			return strings;
    
    		String[] keyMap = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
            
    		int totalComb = 1;
    		for (int i = 0; i < digits.length(); ++i) {
    			totalComb *= keyMap[(digits.charAt(i)) - '0'].length();
    		}
    
    		String comb;
    		int offset;
    		for (int i = 0; i < totalComb; ++i) {
    			offset = totalComb;
    			comb = "";
    			for (int j = 0; j < digits.length(); ++j) {
    				String string = keyMap[digits.charAt(j) - '0'];
    				if (j == digits.length() - 1)
    					comb += string.charAt(i % offset);
    				else {
    					offset = offset / string.length();
    					int idx = i / offset;
    					comb += string.charAt(idx % string.length());
    				}
    			}
    			strings.add(comb);
    		}
    		return strings;
        }
    
    

Log in to reply
 

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