0ms C++ Simple Solution DFS - Good for Beginners


  • 0

    Very Simple DFS Solution.

    String row is passed as copy to each DFS level so you don't have to do a classic backtrack where you push(), DFS, pop() on every loop.
    e.g. row only contains the for loop inside DFS.

    string nums created as index of each location to match that of a phone number (abc at index 2=number 2 on telephone).

    for each element in string digits, it is converted to int and used to index nums, passing each element in nums to row, then proceed recursively.

    if(!digits[st]) return; will automatically return DFS at end of digits

    vector<string> letterCombinations(string digits) {
            if(!digits.size()) return{};
            vector<string> nums={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; //2-9
            vector<string>ans;
            dfs(nums,digits,ans,"",0);
            return ans;
        }
        
        void dfs(const vector<string>& nums, string& digits, vector<string>& ans,string row, int st){
                if(row.size()==digits.size()) {ans.push_back(row); return;}
                if(!digits[st]) return;
                int e=digits[st]-'0';
                for(int i=0; i<nums[e].size(); i++){
                    dfs(nums,digits,ans,row+nums[e][i],st+1);
                }
        }
    

Log in to reply
 

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