Iterative C++ solution


  • 0
    L

    As an alteration of recursive back-tracking seen from most of other answers, this is an iterative approach. The essential idea is to apply queue to push and pop all possible solutions until queue becomes empty. The following shows a simple example of input "abc".

    1. Firstly we push the input inside the empty queue (Qs) and get:
      Qs: {"abc"}
      Also we build a integer queue Qi in order to record the location where we conducted the replacement. We initialize Qi as:
      Qi: {-2}

    2. After that, at the first element of Qs (which is abc), we apply two loop to estimate all abbreviations. The outer loop is used to decide on which character we want to replace by abbreviation. This loop starts from Qi.front()+2 (since replacement can't be adjacent, like "a11") till the end the string.

    The inner loop is used to decide what kind of abbreviation we want to apply (eg. '1','2','3', ...). Every new abbreviated combinations will be pushed into the Qs. So we will get:
    Qs:{abc, 1bc, 2c, 3, a1c, a2, ab1}
    Qi: {-2,0,0,0,1,1,2}

    1. After all "one-time" replacement of "abc" have been saved to Qs, we pop the front element from Qs to the result vector, and pop Qi as well:
      Qs:{1bc, 2c, 3, a1c, a2, ab1}
      Qi:{0,0,0,1,1,2}

    2. Keep looping procedure 2) and 3) until Qs and Qi are empty.

    Additional scenario needed to be noticed is when the string is longer than 9 characters (eg. "interaction"). if replacement becomes "10", "11", etc. The index pushed into Qi must plus 1, at least.

    Hope it's clear.

      class Solution {
        public:
            vector<string> generateAbbreviations(string word) {
                vector<string> res;
                if (!word.size()) {res.push_back(word); return res;}
                queue<string> Qs;
                queue<int> Qi;
                Qs.push(word);
                Qi.push(-2);
                while (!Qs.empty()) {
                    int loc(Qi.front());
                    int nw((Qs.front()).size());
                    for (int i(loc+2);i<nw;i++) {
                        for (int val(1);val<=nw-i;val++) {
                            string str;
                            str+=Qs.front();
                            int cc(replace(str,i,val));
                            Qs.push(str);
                            Qi.push(i+cc);
                            str.clear();
                        }
                    }
                    res.push_back(Qs.front());
                    Qs.pop();
                    Qi.pop();
                }
                return res;
            }
            
        private:
            int replace(string &str, int loc, int val) {
                int i0 = (int)'0';
                string addr;
                int tmp(val);
                int cc(0);
                while (tmp) {
                    addr.insert(0,1,(char)(i0+tmp%10));
                    tmp/=10;
                    cc++;
                }
                str.erase(loc,val);
                str.insert(loc,addr);
                addr.clear();
                return cc-1;
            }
        };

Log in to reply
 

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