Corner case: digit "1"


  • 0
    D

    A lot of solutions given here return a blank set if the input string contains a "1" digit. The reason is: the blank string represented by "1" terminates the DFS.

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            string start;
            vector<string> result;
            dfs(digits, 0, start, result);
            return result;
        }
    
    private:
        void dfs(string& digits, int index, string& current, vector<string>& result) {
            if (index == digits.length()) {
                if (current.length() > 0) {
                    result.push_back(current);
                }
                return;
            }
    
            string chars = Solution::digit_chars[digits[index] - '0'];
            // If the digit is backed by a blank string, we should move on to next digit.
            if (chars.length() == 0) {
                dfs(digits, index + 1, current, result);
            }
            else {
                for (char ch : chars) {
                    current.push_back(ch);
                    dfs(digits, index + 1, current, result);
                    current.pop_back();
                }
            }
        }
    
        const string digit_chars[10] = {
            " ",    /* 0 */
            "",     /* 1 */
            "abc",  /* 2 */
            "def",  /* 3 */
            "ghi",  /* 4 */
            "jkl",  /* 5 */
            "mno",  /* 6 */
            "pqrs", /* 7 */
            "tuv",  /* 8 */
            "wxyz"  /* 9 */
        };
    };
    

Log in to reply
 

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