C++ solution dfs


  • 0
    X
    class Solution {
    public:
        vector<string> generateAbbreviations(string word) {
            string solution = "";
            vector<string> abb;
            dfs(word, solution, 0, word.length(), abb);
            return abb;
        }
        
        void dfs(string word, string solution, int start, int len, vector<string> & abb) {
            if(start >= len) {
                abb.push_back(solution); return;
            }
            
            abb.push_back(solution + word.substr(start, len));
            int numbers = len-start;
            string tmpword="";
            for(int i=1; i <= numbers; i++) {
                for(int j=start; j <= len-i; j++) {
                    tmpword = "";
                    tmpword += word.substr(start, j-start) + to_string(i);
                    if(j != len-i) tmpword += word[j+i];
                    dfs(word, solution+tmpword, j+i+1, len, abb);
                }
            }
        }
    };

Log in to reply
 

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