Accepted C++ code, removing the "unique" assumption by using multimap for indexing


  • 0
    H

    I didn't see the "unique" until I finished it ..
    But anyway I think it can serve as an example to extend to un-unique one.
    Thus this code works for cases like {"aa", "aa", "aa"}.

    The idea is, for every word, decide what's the counter part that can make a palindrome pair.
    Every palindrome has an axle. Try all axle, decide the counter parts (either as first or second in the word pair), and look them up in the indexing map.

    The code should be straightforward. The run time is not so good, 732ms, possibly due to removing of a special duplicate in the end.

    /**
     * Use s as the first part of the palindrome, and assume the axle is decided by {i,on},
     * compute the possible second part.
     *
     * Since it is the first part, and the axle is /in/ it, the other part /must/ be no longer than it.
     * This reads "I only find the other part that is no longer than it."
     * This is /almost/ perfect in removing duplicates.
     * The only situation where we need to remove duplicate is:
     * if 1) string a and b are of /same/ length and
     * 2) both a+b and b+a are polindrome
     *
     * @param [in] s the string
     * @param [in] i the axle index
     * @param [in] on axle is on the index or not. If not, axle is right /after/ index.
     * @param [out] ret return string, the other part
     * @return whether the return is valid for use
     */
    bool as_first(const string &s, int i, bool on, string &ret) {
      if (s.empty()) return true;
      if (i >= (int)s.length()) return false;
      ret.clear();
      // .........k...i...j..
      int j,k;
      if (on) {
        j = i;
        k = i;
      } else {
        j = i+1;
        k = i;
      }
      for (int end=s.length();j<end;j++,k--) {
        if (k<0) return false;
        if (s[j] != s[k]) return false;
      }
      if (k<0) return "";
      ret = s.substr(0, k+1);
      reverse(ret.begin(), ret.end());
      return true;
    }
    
    /**
     * Use s as the second part of the palindrome, and assume the axle is decided by {i,on},
     * compute the possible first part.
     * @param [in] s the string
     * @param [in] i the axle index
     * @param [in] on axle is on the index or not. If not, axle is right /before/ index.
     * @param [out] ret return string, the other part
     * @return whether the return is valid for use
     */
    bool as_second(const string &s, int i, bool on, string &ret) {
      if (s.empty()) return true;
      ret.clear();
      // ..j...i...k........
      int j,k;
      if (on) {
        j = i;
        k = i;
      } else {
        j = i-1;
        k = i;
      }
      for (;j>=0;j--,k++) {
        if (k >= (int) s.length()) return false;
        if (s[j] != s[k]) return false;
      }
      if (k >= (int) s.length()) return "";
      ret = s.substr(k);
      reverse(ret.begin(), ret.end());
      return true;
    }
    
    /**
     * Based on the given string determined by the tuple (place, s, index), its axle (axle, on), and the indices map,
     * Compute all the palindrome that contains it (use it as either first or second word).
     * @param [in] place the place to put this string s, either 0 for first or 1 for second
     * @param [in] s the string under consideration
     * @param [in] index the index of string in original vector
     * @param [in] axle the axle index
     * @param [in] on whether the axle is on the index or not
     * @param [in] words_mm the multimap
     * @param [out] ret valid result will be pushed into this vector
     */
    void solve(int place, const string &s, int index,
               int axle, bool on,
               const multimap<string, int> &words_mm, vector<vector<int> > &ret) {
      bool status=false;
      string other;
      if (place == 0) status = as_first(s, axle, on, other);
      else status = as_second(s, axle, on, other);
    
      if (status) {
        if (words_mm.count(other) > 0) {
          auto range = words_mm.equal_range(other);
          for (auto it=range.first; it!=range.second;it++) {
            if (it->second!=index) {
              if (place == 0) {
                ret.push_back({index, it->second});
              } else {
                ret.push_back({it->second, index});
              }
            }
          }
        }
      }
    }
    
    
    
    class Solution {
    public:
      static vector<vector<int>> palindromePairs(vector<string>& words) {
        vector<vector<int>> ret;
        // this is multimap because the words vector may have duplicate items.
        // e.g. {"aa", "aa", "aa"}
        multimap<string, int> words_mm;
        for (int i=0,end=words.size();i<end;i++) {
          words_mm.emplace(words[i], i);
        }
        for (int idx=0, end=words.size();idx<end;idx++) {
          // if s appear first
          for (int i=words[idx].length(), end=0;i>=end;i--) {
            solve(0, words[idx], idx, i, true, words_mm, ret);
            solve(0, words[idx], idx, i, false, words_mm, ret);
          }
          // if s appear second
          for (int i=0, end=words[idx].length();i<end;i++) {
            solve(1, words[idx], idx, i, true, words_mm, ret);
            solve(1, words[idx], idx, i, false, words_mm, ret);
          }
        }
        /**
         * We need to remove duplicate only in one situation:
         * if 1) string a and b are of /same/ length and
         * 2) both a+b and b+a are polindrome
         */
        set<vector<int> > dup(ret.begin(), ret.end());
        ret.clear();
        ret = vector<vector<int> >(dup.begin(), dup.end());
        return ret;
      }
    };

Log in to reply
 

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