Project Notes

Expression Add Operators

5 min read

Nav: << previous: 281.锯齿迭代器 | next: 283.移动零 >>

Description

tab: English
 
<p>Given a string <code>num</code> that contains only digits and an integer <code>target</code>, return <em><strong>all possibilities</strong> to insert the binary operators </em><code>&#39;+&#39;</code><em>, </em><code>&#39;-&#39;</code><em>, and/or </em><code>&#39;*&#39;</code><em> between the digits of </em><code>num</code><em> so that the resultant expression evaluates to the </em><code>target</code><em> value</em>.</p>
 
<p>Note that operands in the returned expressions <strong>should not</strong> contain leading zeros.</p>
 
<p><strong>Note</strong> that a number can contain multiple digits.</p>
 
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
 
<pre>
<strong>Input:</strong> num = &quot;123&quot;, target = 6
<strong>Output:</strong> [&quot;1*2*3&quot;,&quot;1+2+3&quot;]
<strong>Explanation:</strong> Both &quot;1*2*3&quot; and &quot;1+2+3&quot; evaluate to 6.
</pre>
 
<p><strong class="example">Example 2:</strong></p>
 
<pre>
<strong>Input:</strong> num = &quot;232&quot;, target = 8
<strong>Output:</strong> [&quot;2*3+2&quot;,&quot;2+3*2&quot;]
<strong>Explanation:</strong> Both &quot;2*3+2&quot; and &quot;2+3*2&quot; evaluate to 8.
</pre>
 
<p><strong class="example">Example 3:</strong></p>
 
<pre>
<strong>Input:</strong> num = &quot;3456237490&quot;, target = 9191
<strong>Output:</strong> []
<strong>Explanation:</strong> There are no expressions that can be created from &quot;3456237490&quot; to evaluate to 9191.
</pre>
 
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>
 
<ul>
	<li><code>1 &lt;= num.length &lt;= 10</code></li>
	<li><code>num</code> consists of only digits.</li>
	<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>
</ul>
 
 
 
> [!tip]- Hint 1
> 
> Note that a number can contain multiple digits.
 
> [!tip]- Hint 2
> 
> Since the question asks us to find <b>all</b> of the valid expressions, we need a way to iterate over all of them. (<b>Hint:</b> Recursion!)
 
> [!tip]- Hint 3
> 
> We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion?
 
> [!tip]- Hint 4
> 
> Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators. 



<br> 1 + 2 = 3  <br>

1 + 2 - 4 --> 3 - 4 --> -1 <br>

1 + 2 - 4 * 12 --> -1 * 12 --> -12 (WRONG!) <br>

1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!)
 
> [!tip]- Hint 5
> 
> We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator.
 
 
---
 
[submissions](https://leetcode.com/problems/expression-add-operators/submissions/) | [solutions](https://leetcode.com/problems/expression-add-operators/solutions/)
 
 
tab: 中文
 
<p>给定一个仅包含数字&nbsp;<code>0-9</code>&nbsp;的字符串 <code>num</code> 和一个目标值整数 <code>target</code> ，在 <code>num</code> 的数字之间添加 <strong>二元 </strong>运算符（不是一元）<code>+</code>、<code>-</code>&nbsp;或&nbsp;<code>*</code>&nbsp;，返回 <strong>所有</strong> 能够得到 <code>target</code>&nbsp;的表达式。</p>
 
<p>注意，返回表达式中的操作数 <strong>不应该</strong> 包含前导零。</p>
 
<p><strong>注意</strong>，一个数字可以包含多个数位。</p>
 
<p>&nbsp;</p>
 
<p><strong>示例 1:</strong></p>
 
<pre>
<strong>输入:</strong> <code>num = </code>"123", target = 6
<strong>输出: </strong>["1+2+3", "1*2*3"] 
<strong>解释: </strong>“1*2*3” 和 “1+2+3” 的值都是6。
</pre>
 
<p><strong>示例&nbsp;2:</strong></p>
 
<pre>
<strong>输入:</strong> <code>num = </code>"232", target = 8
<strong>输出: </strong>["2*3+2", "2+3*2"]
<strong>解释:</strong> “2*3+2” 和 “2+3*2” 的值都是8。
</pre>
 
<p><strong>示例 3:</strong></p>
 
<pre>
<strong>输入:</strong> <code>num = </code>"3456237490", target = 9191
<strong>输出: </strong>[]
<strong>解释: </strong>表达式 “3456237490” 无法得到 9191 。
</pre>
 
<p>&nbsp;</p>
 
<p><strong>提示：</strong></p>
 
<ul>
	<li><code>1 &lt;= num.length &lt;= 10</code></li>
	<li><code>num</code> 仅含数字</li>
	<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>
</ul>
 
 
 
> [!tip]- 提示 1
> 
> Note that a number can contain multiple digits.
 
> [!tip]- 提示 2
> 
> Since the question asks us to find <b>all</b> of the valid expressions, we need a way to iterate over all of them. (<b>Hint:</b> Recursion!)
 
> [!tip]- 提示 3
> 
> We can keep track of the expression string and evaluate it at the very end. But that would take a lot of time. Can we keep track of the expression's value as well so as to avoid the evaluation at the very end of recursion?
 
> [!tip]- 提示 4
> 
> Think carefully about the multiply operator. It has a higher precedence than the addition and subtraction operators. 



<br> 1 + 2 = 3  <br>

1 + 2 - 4 --> 3 - 4 --> -1 <br>

1 + 2 - 4 * 12 --> -1 * 12 --> -12 (WRONG!) <br>

1 + 2 - 4 * 12 --> -1 - (-4) + (-4 * 12) --> 3 + (-48) --> -45 (CORRECT!)
 
> [!tip]- 提示 5
> 
> We simply need to keep track of the last operand in our expression and reverse it's effect on the expression's value while considering the multiply operator.
 
 
---
 
[提交记录](https://leetcode.cn/problems/expression-add-operators/submissions/) | [题解](https://leetcode.cn/problems/expression-add-operators/solution/)

Solutions & Notes

properties:
  note.updated:
    displayName: Last Updated
  note.relative_links:
    displayName: Related Links
  note.desc:
    displayName: Description
  note.grade:
    displayName: Rating
  note.program_language:
    displayName: Language
  note.time_complexity:
    displayName: TC
  note.space_complexity:
    displayName: SC
views:
  - type: table
    name: Solutions & Notes
    filters:
      and:
        - file.hasLink(this.file)
        - file.tags.containsAny("leetcode/solution", "leetcode/note")
    order:
      - file.name
      - desc
      - program_language
      - time_complexity
      - space_complexity
      - grade
      - relative_links
      - updated
    sort:
      - property: grade
        direction: ASC
      - property: time_complexity
        direction: ASC
      - property: program_language
        direction: ASC
    columnSize:
      file.name: 104
      note.space_complexity: 65
      note.grade: 126

Similar Problems

properties:
  note.lcTopics:
    displayName: Topics
  note.lcAcRate:
    displayName: AC Rate
  note.favorites:
    displayName: Favorites
  note.grade:
    displayName: Rating
  note.translatedTitle:
    displayName: Title (CN)
  note.lcDifficulty:
    displayName: Difficulty
views:
  - type: table
    name: Similar Problems
    filters:
      and:
        - file.hasLink(this.file)
        - similarQuestions.contains(this.file)
    order:
      - file.name
      - translatedTitle
      - lcTopics
      - lcDifficulty
      - lcAcRate
      - grade
      - favorites
    sort:
      - property: file.name
        direction: ASC
      - property: lcTopics
        direction: DESC
    columnSize:
      note.translatedTitle: 240
      note.lcTopics: 347
      note.lcAcRate: 75
      note.grade: 122

Graph View

Backlinks