leetcode Word Break II

Give two versions of WA code:

Version 1: Runtime Error: Find the bug

class Solution {
 public:
  void find(const string& s, const unordered_set<string>& dict, vector<int>& res) {
    int i, j, len = s.length();
    for (i = 0; i < len; ++i) {
      if (dict.find(s.substr(0, i + 1)) != dict.end()) {
        res.push_back(i);
      }
    }
  }
  void addSpace(vector<string>& cur, vector<vector<string> >& resvec, 
                const string& s, const unordered_set<string>& dict) {
    if (s.length() == 0) {
      resvec.push_back(cur);
      return;
    }
    vector<int> breakpoints;
    find(s, dict, breakpoints);
    for (int i = 0; i < breakpoints.size(); ++i) {
      cur.push_back(s.substr(0, breakpoints[i] + 1));
      addSpace(cur, resvec, s.substr(breakpoints[i]), dict);
      cur.pop_back();
    }
  }
  vector<string> wordBreak(string s, unordered_set<string> &dict) {
    int i, j, size;
    vector<vector<string> > resvec;
    vector<string> res, cur;
    
    addSpace(cur, resvec, s, dict);
    for (i = 0; i < resvec.size(); ++i) {
      string tmp = resvec[i][0];
      for (j = 1; j < resvec[i].size(); ++j) 
        tmp += " " + resvec[i][j];
      res.push_back(tmp);
    }
    return res;
  }
};

class Solution {
 public:
  void find(const string& s, const unordered_set<string>& dict, vector<int>& res) {
    int i, j, len = s.length();
    for (i = 0; i < len; ++i) {
      if (dict.find(s.substr(0, i + 1)) != dict.end()) {
        res.push_back(i);
      }
    }
  }
  void addSpace(vector<string>& cur, vector<vector<string> >& resvec, 
                const string& s, const unordered_set<string>& dict) {
    if (s.length() == 0) {
      resvec.push_back(cur);
      return;
    }
    vector<int> breakpoints;
    find(s, dict, breakpoints);
    for (int i = 0; i < breakpoints.size(); ++i) {
      cur.push_back(s.substr(0, breakpoints[i] + 1));
      addSpace(cur, resvec, s.substr(breakpoints[i] + 1), dict);
      cur.pop_back();
    }
  }
  vector<string> wordBreak(string s, unordered_set<string> &dict) {
    int i, j, size;
    vector<vector<string> > resvec;
    vector<string> res, cur;
    
    addSpace(cur, resvec, s, dict);
    for (i = 0; i < resvec.size(); ++i) {
      string tmp = resvec[i][0];
      for (j = 1; j < resvec[i].size(); ++j) 
        tmp += " " + resvec[i][j];
      res.push_back(tmp);
    }
    return res;
  }
};

class Solution {
 public:
  void find(const string& s, const unordered_set<string>& dict, vector<int>& res) {
    int i, j, len = s.length();
    for (i = 0; i < len; ++i) {
      if (dict.find(s.substr(0, i + 1)) != dict.end()) {
        res.push_back(i);
      }
    }
  }
  void addSpace(vector<string>& cur, vector<vector<string> >& resvec, 
                const string& s, const unordered_set<string>& dict, vector<int>& forbidden) {
    
    if (s.length() == 0) {
      resvec.push_back(cur);
      return;
    }
    if (forbidden[s.length()])
      return;
    vector<int> breakpoints;
    find(s, dict, breakpoints);
    for (int i = 0; i < breakpoints.size(); ++i) {
      cur.push_back(s.substr(0, breakpoints[i] + 1));
      int resvecsize = resvec.size();
      addSpace(cur, resvec, s.substr(breakpoints[i] + 1), dict, forbidden);
      if (resvec.size() == resvecsize)
        forbidden[s.length()-breakpoints[i]-1] = 1;
      cur.pop_back();
    }
  }
  vector<string> wordBreak(string s, unordered_set<string> &dict) {
    int i, j, size;
    vector<vector<string> > resvec;
    vector<string> res, cur;
    vector<int> forbidden(s.length()+1, 0);
    
    addSpace(cur, resvec, s, dict, forbidden);
    for (i = 0; i < resvec.size(); ++i) {
      string tmp = resvec[i][0];
      for (j = 1; j < resvec[i].size(); ++j) 
        tmp += " " + resvec[i][j];
      res.push_back(tmp);
    }
    return res;
  }
};

leetcode Word Break II,布布扣,bubuko.com

leetcode Word Break II

原文：http://blog.csdn.net/taoqick/article/details/38357329