回溯题目：口算难题

文章目录

题目
- 标题和出处
- 难度
- 题目描述
- - 要求
  - 示例
  - 数据范围
解法
- 思路和算法
- 代码
- 复杂度分析
拓展问题
- 题目描述
- 解法分析
- 代码
- 复杂度分析

题目

标题和出处

标题：口算难题

出处：1307. 口算难题

难度

9 级

题目描述

要求

给定一个方程，左边用

words

\\texttt{words}

$words$ 表示，右边用

result

\\texttt{result}

$result$ 表示。

需要根据以下规则检查方程是否可解：

每个字符都会被解码成一位数字（ $\\texttt{0} 0 到 9 \\texttt{9} 9）。$
不同的字符必须映射到不同的数字。
每个 $\\texttt{words[i]} words[i] 和 result \\texttt{result} result 都会被解码成一个没有前导零的数字。$
左侧数字（ $\\texttt{words} words）之和等于右侧数字（ result \\texttt{result} result）。$

如果方程可解，返回

true

\\texttt{true}

$true$ ，否则返回

false

\\texttt{false}

$false$ 。

示例

示例 1：

输入：

words

["SEND","MORE"],

result

"MONEY"

\\texttt{words = ["SEND","MORE"], result = "MONEY"}

$words = ["SEND","MORE"], result = "MONEY"$ 输出：

true

\\texttt{true}

$true$ 解释：映射

‘S’

→

\\texttt{`S'} \\rightarrow \\texttt{9}

$‘S’ \to 9$ ，

‘E’

→

\\texttt{`E'} \\rightarrow \\texttt{5}

$‘E’ \to 5$ ，

‘N’

→

\\texttt{`N'} \\rightarrow \\texttt{6}

$‘N’ \to 6$ ，

‘D’

→

\\texttt{`D'} \\rightarrow \\texttt{7}

$‘D’ \to 7$ ，

‘M’

→

\\texttt{`M'} \\rightarrow \\texttt{1}

$‘M’ \to 1$ ，

‘O’

→

\\texttt{`O'} \\rightarrow \\texttt{0}

$‘O’ \to 0$ ，

‘R’

→

\\texttt{`R'} \\rightarrow \\texttt{8}

$‘R’ \to 8$ ，

‘Y’

→

\\texttt{`Y'} \\rightarrow \\texttt{2}

$‘Y’ \to 2$ 。方程为

"SEND"

"MORE"

"MONEY"

\\texttt{"SEND"} + \\texttt{"MORE"} = \\texttt{"MONEY"}

$"SEND" + "MORE" = "MONEY"$ ，方程的解为

9567

1085

10652

\\texttt{9567} + \\texttt{1085} = \\texttt{10652}

$9567 + 1085 = 10652$ 。

示例 2：

输入：

words

["SIX","SEVEN","SEVEN"],

result

"TWENTY"

\\texttt{words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"}

$words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"$ 输出：

true

\\texttt{true}

$true$ 解释：映射

‘S’

→

\\texttt{`S'} \\rightarrow \\texttt{6}

$‘S’ \to 6$ ，

‘I’

→

\\texttt{`I'} \\rightarrow \\texttt{5}

$‘I’ \to 5$ ，

‘X’

→

\\texttt{`X'} \\rightarrow \\texttt{0}

$‘X’ \to 0$ ，

‘E’

→

\\texttt{`E'} \\rightarrow \\texttt{8}

$‘E’ \to 8$ ，

‘V’

→

\\texttt{`V'} \\rightarrow \\texttt{7}

$‘V’ \to 7$ ，

‘N’

→

\\texttt{`N'} \\rightarrow \\texttt{2}

$‘N’ \to 2$ ，

‘T’

→

\\texttt{`T'} \\rightarrow \\texttt{1}

$‘T’ \to 1$ ，

‘W’

→

’3’

\\texttt{`W'} \\rightarrow \\texttt{'3'}

$‘W’ \to ’3’$ ，

‘Y’

→

\\texttt{`Y'} \\rightarrow \\texttt{4}

$‘Y’ \to 4$ 。方程为

"SIX"

"SEVEN"

"TWENTY"

\\texttt{"SIX"} + \\texttt{"SEVEN"} + \\texttt{"SEVEN"} = \\texttt{"TWENTY"}

$"SIX" + "SEVEN" + "SEVEN" = "TWENTY"$ ，方程的解为

650

68782

138214

\\texttt{650} + \\texttt{68782} + \\texttt{68782} = \\texttt{138214}

$650 + 68782 + 68782 = 138214$ 。

示例 3：

输入：

words

["LEET","CODE"],

result

"POINT"

\\texttt{words = ["LEET","CODE"], result = "POINT"}

$words = ["LEET","CODE"], result = "POINT"$ 输出：

false

\\texttt{false}

$false$ 解释：不存在满足方程的映射，所以返回

false

\\texttt{false}

$false$ 。注意不同的字母不能映射到相同的数字。

数据范围

$\\texttt{2} \\le \\texttt{words.length} \\le \\texttt{5} 2≤words.length≤5$
$\\texttt{1} \\le \\texttt{words[i].length, results.length} \\le \\texttt{7} 1≤words[i].length, results.length≤7$
$\\texttt{words[i], result} words[i], result 只含有大写英语字母$
表达式中使用的不同字符数最大为 $\\texttt{10} 10$

解法

思路和算法

这道题要求判断给定的方程是否可解，需要枚举所有可能的字母和数字之间的映射关系，使用回溯的做法判断。如果回溯过程中没有剪枝，则可能的映射关系为阶乘级，时间复杂度过高。因此，回溯过程中需要使用剪枝减少搜索空间，排除不可能的情况。

首先将方程中的所有的数都移到等号左边，使等号右边等于

$0$ ，并对每个字母合并同类项，得到每个字母对应的系数，然后分别枚举每个字母可能映射到的数字。如果一个字母的系数绝对值越大，则该字母可能映射到的数字越少，因此为了减少搜索空间，应按照系数绝对值从大到小的顺序分别枚举每个字母可能映射到的数字。

为了按照系数绝对值从大到小的顺序枚举，需要将所有字母按照系数的正负性分成两组，同一组中的字母按照系数的绝对值从大到小的顺序排序。系数为零的字母可以忽略，理由如下。

系数为零的字母取任何值都不会改变方程的值。

方程中的不同字母数最大为

$10$ ，因此当系数不为零的字母取值都确定之后，系数为零的字母一定可以取到和其他字母都不重复的取值。

回溯过程中，每次取尚未遍历的字母中的系数绝对值最大的字母，如果同时存在最大绝对值的正系数和负系数则取正系数。每个字母的取值范围是

[

]

[0, 9]

$[0, 9]$ 中的整数，不同字母的取值不同，并满足以下两个条件。

如果一个字母位于多位数的最高位，则该字母的取值不能是

$0$ 。

遍历到的字母的取值存在上界，如果符号相反的尚未遍历的字母的系数加权和的绝对值最大时，方程的等号左边的符号仍为当前字母的符号，则当前字母的取值过大。

考虑示例 1 的方程，其形式为

SEND

‾

MONEY

‾

\\overline{\\text{SEND}} + \\overline{\\text{MORE}} = \\overline{\\text{MONEY}}

$\overline{SEND} + \overline{MORE} = \overline{MONEY}$ 。将所有的数都移到等号左边，得到

SEND

‾

−

MONEY

‾

\\overline{\\text{SEND}} + \\overline{\\text{MORE}} – \\overline{\\text{MONEY}} = 0

$\overline{SEND} + \overline{MORE} - \overline{MONEY} = 0$ ，然后合并同类项。

(

1000

100

)

(

1000

100

)

−

(

10000

1000

100

)

1000

−

9000

−

900

−

\\begin{aligned} (1000 \\times \\text{S} + 100 \\times \\text{E} + 10 \\times \\text{N} + 1 \\times \\text{D}) + (1000 \\times \\text{M} + 100 \\times \\text{O} + 10 \\times \\text{R} + 1 \\times \\text{E}) \\\\ -(10000 \\times \\text{M} + 1000 \\times \\text{O} + 100 \\times \\text{N} + 10 \\times \\text{E} + 1 \\times \\text{Y}) &= 0 \\\\ 1000 \\times \\text{S} + 91 \\times \\text{E} + 10 \\times \\text{R} + 1 \\times \\text{D} – 9000 \\times \\text{M} – 900 \\times \\text{O} – 90 \\times \\text{N} – 1 \\times \\text{Y} &= 0 \\end{aligned}

$(1000 \times S + 100 \times E + 10 \times N + 1 \times D) + (1000 \times M + 100 \times O + 10 \times R + 1 \times E) - (10000 \times M + 1000 \times O + 100 \times N + 10 \times E + 1 \times Y) 1000 \times S + 91 \times E + 10 \times R + 1 \times D - 9000 \times M - 900 \times O - 90 \times N - 1 \times Y = 0 = 0$

回溯时首先考虑系数绝对值最大的字母

\\text{M}

$M$ ，对应系数

−

9000

-9000

$- 9000$ 。尚未遍历的正系数字母的系数加权和的最大值（对应最大绝对值）为

1000

9804

1000 \\times 9 + 91 \\times 8 + 10 \\times 7 + 1 \\times 6 = 9804

$1000 \times 9 + 91 \times 8 + 10 \times 7 + 1 \times 6 = 9804$ ，因此

\\text{M}

$M$ 的取值上界是

⌊

9804

9000

⌋

\\Big\\lfloor \\dfrac{9804}{9000} \\Big\\rfloor = 1

$⌊ \frac{9804}{9000} ⌋ = 1$ 。由于

\\text{M}

$M$ 位于最高位因此取值下界是

$1$ 。因此

\\text{M}

$M$ 的值等于

$1$ 。

确定

\\text{M} = 1

$M = 1$ 之后，考虑剩余字母中系数绝对值最大的字母

\\text{S}

$S$ ，对应系数

1000

$1000$ 。尚未遍历的负系数字母的系数加权和的最小值（对应最大绝对值）为

(

−

900

)

(

−

)

(

−

)

−

8827

(-900) \\times 9 + (-90) \\times 8 + (-1) \\times 7 = -8827

$(- 900) \times 9 + (- 90) \times 8 + (- 1) \times 7 = - 8827$ ，计算

\\text{S}

$S$ 的取值上界时需要考虑已经遍历过的

\\text{M}

$M$ 的取值，因此

\\text{S}

$S$ 的取值上界是

⌊

9000

8827

1000

⌋

\\Big\\lfloor \\dfrac{9000 + 8827}{1000} \\Big\\rfloor = 17

$⌊ \frac{9000 + 8827}{1000} ⌋ = 17$ ，该上界大于

$9$ 因此

\\text{S}

$S$ 的取值上界是

$9$ 。由于

\\text{S}

$S$ 位于最高位因此取值下界是

$1$ 。因此

\\text{S}

$S$ 的取值范围是

[

]

[1, 9]

$[1, 9]$ 。由于已经有

\\text{M} = 1

$M = 1$ ，为了确保不同字母的取值不同，后续回溯时会跳过

\\text{S} = 1

$S = 1$ 的情况。

其余字母的回溯做法相同。由于方程存在解

9567

1085

10652

9567 + 1085 = 10652

$9567 + 1085 = 10652$ ，因此返回

true

\\text{true}

$true$ 。

代码

class Solution {
class LetterCoefficient {
private char letter;
private int coefficient;

public LetterCoefficient(char letter, int coefficient) {
this.letter = letter;
this.coefficient = coefficient;
}

public char getLetter() {
return letter;
}

public int getCoefficient() {
return coefficient;
}
}

Set<Character> leading = new HashSet<Character>();
boolean[] used = new boolean[10];
Map<Character, Integer> coefficients = new HashMap<Character, Integer>();
int positiveCount, negativeCount;
List<LetterCoefficient> positiveList = new ArrayList<LetterCoefficient>();
List<LetterCoefficient> negativeList = new ArrayList<LetterCoefficient>();
List<Integer> positiveBounds = new ArrayList<Integer>();
List<Integer> negativeBounds = new ArrayList<Integer>();

public boolean isSolvable(String[] words, String result) {
for (String word : words) {
handleNum(word, 1);
}
handleNum(result, –1);
Set<Map.Entry<Character, Integer>> entries = coefficients.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
char letter = entry.getKey();
int coefficient = entry.getValue();
LetterCoefficient lc = new LetterCoefficient(letter, coefficient);
if (coefficient > 0) {
positiveList.add(lc);
} else if (coefficient < 0) {
negativeList.add(lc);
}
}
positiveCount = positiveList.size();
negativeCount = negativeList.size();
Collections.sort(positiveList, (a, b) -> b.getCoefficient() – a.getCoefficient());
Collections.sort(negativeList, (a, b) -> a.getCoefficient() – b.getCoefficient());
for (int i = 0; i < positiveCount; i++) {
int bound = 0;
for (int j = i, val = 9; j < positiveCount; j++, val—) {
bound += positiveList.get(j).getCoefficient() * val;
}
positiveBounds.add(bound);
}
positiveBounds.add(0);
for (int i = 0; i < negativeCount; i++) {
int bound = 0;
for (int j = i, val = 9; j < negativeCount; j++, val—) {
bound += negativeList.get(j).getCoefficient() * val;
}
negativeBounds.add(bound);
}
negativeBounds.add(0);
return backtrack(0, 0, 0);
}

public void handleNum(String word, int sign) {
int wordLength = word.length();
if (wordLength > 1) {
leading.add(word.charAt(0));
}
for (int i = wordLength – 1, unit = sign; i >= 0; i—, unit *= 10) {
char letter = word.charAt(i);
coefficients.put(letter, coefficients.getOrDefault(letter, 0) + unit);
}
}

public boolean backtrack(int total, int positiveIndex, int negativeIndex) {
if (positiveIndex == positiveCount && negativeIndex == negativeCount) {
return total == 0;
}
boolean positive;
if (negativeIndex == negativeCount) {
if (total > 0) {
return false;
}
positive = true;
} else if (positiveIndex == positiveCount) {
if (total < 0) {
return false;
}
positive = false;
} else {
positive = positiveList.get(positiveIndex).getCoefficient() + negativeList.get(negativeIndex).getCoefficient() >= 0;
}
List<LetterCoefficient> currList = positive ? positiveList : negativeList;
int currIndex = positive ? positiveIndex : negativeIndex;
List<Integer> bounds = positive ? negativeBounds : positiveBounds;
int boundIndex = positive ? negativeIndex : positiveIndex;
int positiveIncrease = positive ? 1 : 0;
int negativeIncrease = positive ? 0 : 1;
LetterCoefficient lc = currList.get(currIndex);
char letter = lc.getLetter();
int coefficient = lc.getCoefficient();
int currBound = –bounds.get(boundIndex) – total;
int minVal = leading.contains(letter) ? 1 : 0;
int maxVal = Math.min(currBound / coefficient, 9);
for (int i = minVal; i <= maxVal; i++) {
if (!used[i]) {
used[i] = true;
int newTotal = total + coefficient * i;
if (backtrack(newTotal, positiveIndex + positiveIncrease, negativeIndex + negativeIncrease)) {
return true;
}
used[i] = false;
}
}
return false;
}
}

复杂度分析

时间复杂度：

O

(

L

+

n

×

A

10

n

)

O(L + n \\times A_{10}^n)

$O (L + n \times A_{10}^{n})$ ，其中

L

L

$L$ 是方程中的所有数字长度之和，

n

n

$n$ 是方程中的不同字母个数。合并同类项需要

O

(

L

)

O(L)

$O (L)$ 的时间，合并同类项之后，所有字母的取值有

A

10

n

A_{10}^n

$A_{10}^{n}$ 种，对于每种取值需要

O

(

n

)

O(n)

$O (n)$ 的时间判断是否为方程的解，因此时间复杂度是

O

(

L

+

n

×

A

10

n

)

O(L + n \\times A_{10}^n)

$O (L + n \times A_{10}^{n})$ 。
空间复杂度：

O

(

n

)

O(n)

$O (n)$ ，其中

n

n

$n$ 是方程中的不同字母个数。回溯过程中使用的空间和递归调用栈需要

O

(

n

)

O(n)

$O (n)$ 的空间。

拓展问题

题目描述

原始问题中的数字全部由字母组成，只有判断方程是否可解，在原始问题的基础上，可以提出两个拓展问题。

如果方程中有已知的数字，如何判断方程是否可解？

方程的解是什么？如果有多种解，返回其中任意一种。如果方程不可解，返回空字符串。

解法分析

第 1 个拓展问题，方程中存在常数项，在合并同类项的时候计算常数项，回溯时有一个初始的常数项，做法和原始问题相同。

第 2 个拓展问题，为了得到方程的解，需要使用哈希表记录每个字母的取值。回溯过程中，对于当前字母的每个取值，将其存入哈希表，然后继续回溯。如果存在字母的取值满足方程，则根据每个字母的取值生成方程的解。

为了确保每个字母都有取值，系数为零的字母不可以忽略，可以将系数为零的字母与系数为正的字母分在同一组，即所有的字母分成系数为非负数和系数为负数两组。

如果方程中有已知的数字，在生成方程的解时，对于已知的数字直接输出即可。

代码

下面的代码是第 1 个拓展问题的实现。

class Solution {
class LetterCoefficient {
private char letter;
private int coefficient;

public LetterCoefficient(char letter, int coefficient) {
this.letter = letter;
this.coefficient = coefficient;
}

public char getLetter() {
return letter;
}

public int getCoefficient() {
return coefficient;
}
}

Set<Character> leading = new HashSet<Character>();
boolean[] used = new boolean[10];
int constantSum = 0;
Map<Character, Integer> coefficients = new HashMap<Character, Integer>();
int positiveCount, negativeCount;
List<LetterCoefficient> positiveList = new ArrayList<LetterCoefficient>();
List<LetterCoefficient> negativeList = new ArrayList<LetterCoefficient>();
List<Integer> positiveBounds = new ArrayList<Integer>();
List<Integer> negativeBounds = new ArrayList<Integer>();

public void handleNum(String word, int sign) {
int wordLength = word.length();
if (wordLength > 1) {
leading.add(word.charAt(0));
}
for (int i = wordLength – 1, unit = sign; i >= 0; i—, unit *= 10) {
if (Character.isDigit(word.charAt(i))) {
constantSum += (word.charAt(i) – '0') * unit;
} else {
char letter = word.charAt(i);
coefficients.put(letter, coefficients.getOrDefault(letter, 0) + unit);
}
}
}

下面的代码是方程中全部是字母的情况的第 2 个拓展问题的实现。返回值是一个字符串，表示方程的解的加法形式。

class Solution {
class LetterCoefficient {
private char letter;
private int coefficient;

public LetterCoefficient(char letter, int coefficient) {
this.letter = letter;
this.coefficient = coefficient;
}

public char getLetter() {
return letter;
}

public int getCoefficient() {
return coefficient;
}
}

String equationSolution = "";
String[] words;
String result;
Set<Character> leading = new HashSet<Character>();
boolean[] used = new boolean[10];
Map<Character, Integer> coefficients = new HashMap<Character, Integer>();
Map<Character, Integer> letterDigits = new HashMap<Character, Integer>();
int positiveCount, negativeCount;
List<LetterCoefficient> positiveList = new ArrayList<LetterCoefficient>();
List<LetterCoefficient> negativeList = new ArrayList<LetterCoefficient>();
List<Integer> positiveBounds = new ArrayList<Integer>();
List<Integer> negativeBounds = new ArrayList<Integer>();

public String isSolvable(String[] words, String result) {
this.words = words;
this.result = result;
for (String word : words) {
handleNum(word, 1);
}
handleNum(result, –1);
Set<Map.Entry<Character, Integer>> entries = coefficients.entrySet();
for (Map.Entry<Character, Integer> entry : entries) {
char letter = entry.getKey();
int coefficient = entry.getValue();
LetterCoefficient lc = new LetterCoefficient(letter, coefficient);
if (coefficient >= 0) {
positiveList.add(lc);
} else {
negativeList.add(lc);
}
}
positiveCount = positiveList.size();
negativeCount = negativeList.size();
Collections.sort(positiveList, (a, b) -> b.getCoefficient() – a.getCoefficient());
Collections.sort(negativeList, (a, b) -> a.getCoefficient() – b.getCoefficient());
for (int i = 0; i < positiveCount; i++) {
int bound = 0;
for (int j = i, val = 9; j < positiveCount; j++, val—) {
bound += positiveList.get(j).getCoefficient() * val;
}
positiveBounds.add(bound);
}
positiveBounds.add(0);
for (int i = 0; i < negativeCount; i++) {
int bound = 0;
for (int j = i, val = 9; j < negativeCount; j++, val—) {
bound += negativeList.get(j).getCoefficient() * val;
}
negativeBounds.add(bound);
}
negativeBounds.add(0);
backtrack(0, 0, 0);
return equationSolution;
}

public boolean backtrack(int total, int positiveIndex, int negativeIndex) {
if (positiveIndex == positiveCount && negativeIndex == negativeCount) {
boolean flag = total == 0;
if (flag) {
equationSolution = generateEquationSolution();
}
return flag;
}
boolean positive;
if (negativeIndex == negativeCount) {
if (total > 0) {
return false;
}
positive = true;
} else if (positiveIndex == positiveCount) {
if (total < 0) {
return false;
}
positive = false;
} else {
positive = positiveList.get(positiveIndex).getCoefficient() + negativeList.get(negativeIndex).getCoefficient() >= 0;
}
List<LetterCoefficient> currList = positive ? positiveList : negativeList;
int currIndex = positive ? positiveIndex : negativeIndex;
List<Integer> bounds = positive ? negativeBounds : positiveBounds;
int boundIndex = positive ? negativeIndex : positiveIndex;
int positiveIncrease = positive ? 1 : 0;
int negativeIncrease = positive ? 0 : 1;
LetterCoefficient lc = currList.get(currIndex);
char letter = lc.getLetter();
int coefficient = lc.getCoefficient();
int currBound = –bounds.get(boundIndex) – total;
int minVal = leading.contains(letter) ? 1 : 0;
int maxVal = coefficient != 0 ? Math.min(currBound / coefficient, 9) : 9;
for (int i = minVal; i <= maxVal; i++) {
if (!used[i]) {
used[i] = true;
letterDigits.put(letter, i);
int newTotal = total + coefficient * i;
if (backtrack(newTotal, positiveIndex + positiveIncrease, negativeIndex + negativeIncrease)) {
return true;
}
used[i] = false;
letterDigits.remove(letter);
}
}
return false;
}

public String generateEquationSolution() {
StringBuffer sb = new StringBuffer();
for (String word : words) {
if (sb.length() > 0) {
sb.append(" + ");
}
int wordLength = word.length();
for (int i = 0; i < wordLength; i++) {
char letter = word.charAt(i);
sb.append(letterDigits.get(letter));
}
}
sb.append(" = ");
int resultLength = result.length();
for (int i = 0; i < resultLength; i++) {
char letter = result.charAt(i);
sb.append(letterDigits.get(letter));
}
return sb.toString();
}
}

下面的代码是方程中有已知的数字的情况的第 2 个拓展问题的实现。返回值是一个字符串，表示方程的解的加法形式。

class Solution {
class LetterCoefficient {
private char letter;
private int coefficient;

public LetterCoefficient(char letter, int coefficient) {
this.letter = letter;
this.coefficient = coefficient;
}

public char getLetter() {
return letter;
}

public int getCoefficient() {
return coefficient;
}
}

String equationSolution = "";
String[] words;
String result;
Set<Character> leading = new HashSet<Character>();
boolean[] used = new boolean[10];
int constantSum = 0;
Map<Character, Integer> coefficients = new HashMap<Character, Integer>();
Map<Character, Integer> letterDigits = new HashMap<Character, Integer>();
int positiveCount, negativeCount;
List<LetterCoefficient> positiveList = new ArrayList<LetterCoefficient>();
List<LetterCoefficient> negativeList = new ArrayList<LetterCoefficient>();
List<Integer> positiveBounds = new ArrayList<Integer>();
List<Integer> negativeBounds = new ArrayList<Integer>();

public void handleNum(String word, int sign) {
int wordLength = word.length();
if (wordLength > 1) {
leading.add(word.charAt(0));
}
for (int i = wordLength – 1, unit = sign; i >= 0; i—, unit *= 10) {
if (Character.isDigit(word.charAt(i))) {
constantSum += (word.charAt(i) – '0') * unit;
} else {
char letter = word.charAt(i);
coefficients.put(letter, coefficients.getOrDefault(letter, 0) + unit);
}
}
}

public String generateEquationSolution() {
StringBuffer sb = new StringBuffer();
for (String word : words) {
if (sb.length() > 0) {
sb.append(" + ");
}
int wordLength = word.length();
for (int i = 0; i < wordLength; i++) {
if (Character.isDigit(word.charAt(i))) {
sb.append(word.charAt(i));
} else {
char letter = word.charAt(i);
sb.append(letterDigits.get(letter));
}
}
}
sb.append(" = ");
int resultLength = result.length();
for (int i = 0; i < resultLength; i++) {
if (Character.isDigit(result.charAt(i))) {
sb.append(result.charAt(i));
} else {
char letter = result.charAt(i);
sb.append(letterDigits.get(letter));
}
}
return sb.toString();
}
}

复杂度分析

时间复杂度：

O

(

L

+

n

×

A

10

n

)

O(L + n \\times A_{10}^n)

$O (L + n \times A_{10}^{n})$ ，其中

L

L

$L$ 是方程中的所有数字长度之和，

n

n

$n$ 是方程中的不同字母个数。回溯过程中每次更新取值哈希表的时间是

O

(

1

)

O(1)

$O (1)$ ，生成方程的解需要

O

(

L

)

O(L)

$O (L)$ 的时间，因此和原始问题的时间复杂度相同。
空间复杂度：

O

(

n

)

O(n)

$O (n)$ ，其中

n

n

$n$ 是方程中的不同字母个数。记录每个字母的取值的哈希表需要

O

(

n

)

O(n)

$O (n)$ 的空间，因此和原始问题的空间复杂度相同。

文章目录

题目

标题和出处

难度

题目描述

要求

示例

数据范围

解法

思路和算法

代码

复杂度分析

拓展问题

题目描述

解法分析

代码

复杂度分析

相关推荐

评论抢沙发

评论前必须登录！

热门标签

置顶推荐

热门文章

最新文章

文章目录

题目

标题和出处

难度

题目描述

要求

示例

数据范围

解法

思路和算法

代码

复杂度分析

拓展问题

题目描述

解法分析

代码

复杂度分析

相关推荐

评论 抢沙发

评论前必须登录！

热门标签

置顶推荐

热门文章

最新文章

评论抢沙发