[Leetcode]282. Expression Add Operators(C++)

题目描述

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

例子

例子 1

Input: num = "123", target = 6 Output: ["1+2+3", "1*2*3"]

例子 2

Input: num = "232", target = 8 Output: ["2*3+2", "2+3*2"]

例子 3

Input: num = "105", target = 5 Output: ["1*0+5","10-5"]

Constraints

0 <= num.length <= 10

num only contain digits.

解题思路

这道题要用回溯的思路做，从字符串开头进行遍历，每遍历一个位置作为一个状态，从当前位置可以获得一个数字，接下里可以进行以下操作：

从当前位置继续遍历字符串并将其后续字符也纳入到当前的数字中
进行 + 操作，具体方法是将前一状态的结果加上当前数字，并递归调用本函数，传入更新后的路径以及路径结果，同时还需要将当前添加的新数字传入（这一步后面解释用法）
进行 - 操作，具体方法同上类似，加法换成乘法即可，新添加的数字要传入当前的数字的相反数，表示是一个减操作
进行 * 操作，这一步由于要考虑优先级，因此我们要先在前一状态结果中去除上一步操作（即前两部传入新添加的数字的作用），做法是 前一状态结果 - 新添加的元素，接下来进行： 更新后的前状态 + 新添加元素 * 当前数字，同样将 新添加元素 * 当前数字 作为当前操作数传入递归函数。

有几个地方需要注意下：

凡是涉及到字符串转数字都需要考虑数字长度问题，在这道题目下字符串长度不超过 10，因此用 long 表示结果即可
经过测试, 01 之类的数字不合法，因此在循环中需要考虑去除以 0 开头的数字情况
在初识状态时（路径为空，或者索引是 0）不需要进行操作.

代码如下：

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::string> addOperators(std::string num, int target) {

        m_target = target;
        std::string path;
        generatePath(num, 0, path, 0, 0);

        return m_result;
    }

private:
    std::vector<std::string> m_result;
    int m_target;

    void generatePath(const std::string& num, int idx, std::string& path, long curr_eval, long prev_eval) {
        if (idx == num.length()) {
            if (curr_eval == m_target) {
                m_result.push_back(path);
            }
            return;
        }

        long candidate = 0;
        for (int i = idx; i < num.length(); ++i) {
            if (i != idx && num[idx] == '0') break; // number begins with 0 and not 0 (e.g 01) is invalid

            candidate *= 10;
            candidate += (num[i] - '0');

            std::string candidate_str = std::to_string(candidate);
            if (idx == 0) {
                // if this is the beginning of path, (e.g path == ""), no previous operator is required
                path += candidate_str;
                generatePath(num, i + 1, path, candidate, candidate);
                path.erase(path.length() - candidate_str.length());
            }
            else {
                // #1 : addition
                path += "+";
                path += candidate_str;
                generatePath(num, i + 1, path, curr_eval + candidate, candidate);
                
                // #2 : substraction
                path[path.length() - candidate_str.length() - 1] = '-';
                generatePath(num, i + 1, path, curr_eval - candidate, - candidate);

                // #3 : multiplication
                path[path.length() - candidate_str.length() - 1] = '*';
                generatePath(num, i + 1, path, curr_eval - prev_eval + prev_eval * candidate, prev_eval * candidate);

                // reset path by erase operator and new number
                path.erase(path.length() - candidate_str.length() - 1);
            }
        }
    }
};

时间复杂度: O(2^n)
空间复杂度: O(2^n)

GitHub 代码同步地址： 282.ExpressionAddOperators.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions