LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 回溯法，通常写法如下

void dfs(..., int n) {  // 定义一个不断增长的参数
  if (n 满足某个条件，到达终点) {
    进行一些操作;
    return;
  }
  // 否则执行一些操作再进入下一步，结束后撤销操作
  操作 1;
  dfs(..., n + 1);  // 进入下一步
  撤销操作 1;
}

• 解法如下

class Solution {
 public:
  vector<string> letterCombinations(string digits) {
    vector<string> res;
    if (empty(digits)) {
      return res;
    }
    dfs(digits, res, 0, "");
    return res;
  }

  void dfs(string digits, vector<string>& res, int n, string s) {
    if (n == size(digits)) {  // 遍历结束
      res.emplace_back(s);    // 记录结果
      return;
    }
    for (auto& x : key[digits[n] - '2']) {
      s += x;  // 操作 1
      dfs(digits, res, n + 1, s);
      s.pop_back();  // 撤销操作 1，回溯到操作 1 之前的状态
    }
  }

 private:
  const vector<string> key{"abc", "def",  "ghi", "jkl",
                           "mno", "pqrs", "tuv", "wxyz"};
};