Posted on by seeker

LeetCode – 17 : Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

[code lang="java"]
class Solution {
    public List<String> letterCombinations(String digits) {
        
    }
}
[code]

Idea – 1

If there are n digits each having m possible substitutions, there are O(n^m) combinations in total. We generate each through dfs. Time complexity is O(n^m\cdot n) and space complexity due to recursion stack (excluding output size) is O(n). 
[code lang="java"]
class Solution {
    private static final String[] map = 
        {
            "", 
            "", 
            "abc", // 2
            "def", // 3
            "ghi", // 4
            "jkl", // 5
            "mno", // 6
            "pqrs", // 7
            "tuv", // 8
            "wxyz" // 9
        };
    
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        
        if(digits.isEmpty())
        {
            return ans;
        }
        
        collect(digits, 0, "", ans);
        return ans;
    }
    
    private void collect(String digits, int i, String buffer, List<String> ans)
    {
        if(i >= digits.length())
        {
            ans.add(buffer);
            return;
        }
        
        char c = digits.charAt(i);
        String subst = map[c-'0'];
        for(int j = 0; j < subst.length(); ++j)
        {
            collect(digits, i+1, buffer+subst.charAt(j), ans);
        }
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Letter Combinations of a Phone Number.Memory Usage: 35.1 MB, less than 98.08% of Java online submissions for Letter Combinations of a Phone Number.

Posted on by seeker

LeetCode – 9 : Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        
    }
}
[code]

Idea – 1

If a number has a negative sign, it cannot be a palindrome number. Otherwise, we match digits from the two ends. Time complexity is O\left(\log_{10} n\right) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0)
        {
            return false;
        }
        
        // single digit is palindrome
        if(x < 10)
        {
            return true;
        }
        
        int j = (int)Math.log10(x);
        int i = 0;
        
        while(i < j)
        {
            if(getDigit(x, i++) != getDigit(x, j--))
            {
                return false;
            }
        }
        
        return true;
    }
    
    private int getDigit(int x, int i)
    {
       int msbExponent = (int)Math.log10(x);    
       int msbPower = (int)Math.pow(10, msbExponent);
        
       if(i == msbExponent)
       {
           return x/msbPower;
       }
        
       int MOD = (int)Math.pow(10, i+1);
       int ans = x%MOD;
       int DIV = (int)Math.pow(10, i);
       ans /= DIV;
        
       return ans;
    }
}
[code]

Runtime: 27 ms, faster than 57.69% of Java online submissions for Palindrome Number.Memory Usage: 34.9 MB, less than 80.99% of Java online submissions for Palindrome Number.