Multiply Two Strings in Java

Java 中将两个字符串相乘涉及将表示数字的字符串转换为整数值，执行乘法，然后将结果转换回字符串。这种方法在处理超出 int 或 long 等原始数据类型范围的非常大的数字时特别有用。

输入：字符串 1 = "123"，字符串 2 = "45"

输出"5535"

解释

通过将 "123" 和 "45" 作为 整数 相乘，得到输出 "5535"。类似于手动计算的逐位乘法会产生中间和，然后将它们组合起来形成最终的乘积。然后将结果转换回字符串，准确地表示两个输入字符串作为数字的乘法。

方法 1：使用结果数组进行逐位乘法

算法

步骤 1：处理边缘情况：检查两个 字符串 中是否有任何一个是 "0"。如果是，则立即返回 "0"，因为任何数乘以零都得零。

步骤 1.1：检查零输入：如果任一输入字符串（num1 或 num2）等于 "0"，则乘积始终为 "0"。这是因为任何数乘以零都得零。在这种情况下，无需进一步计算，立即返回 "0"。此步骤可确保效率并避免不必要的处理。

步骤 2：初始化变量：计算两个输入字符串 num1 和 num2 的长度。创建一个大小为 n1 + n2 的整数 数组 result，用于存储乘法的中间结果和最终结果。此大小可确保它能够容纳两个数字的最大可能乘积。

步骤 2.1：计算输入字符串的长度：首先计算两个输入字符串 num1 和 num2 的长度。这对于确定结果数组的大小至关重要。结果数组的大小应足以容纳最大可能的乘积，其长度可能为 n1 + n2。

步骤 3：模拟手动乘法：从右到左循环 num1 的数字（类似于手动乘法）。对于 num1 中的每个数字，从右到左循环 num2 的数字。将 num1 和 num2 的当前数字相乘。这将得到一个部分乘积。

步骤 4：将部分乘积添加到结果数组：计算部分乘积在结果数组中的贡献位置。它取决于 num1 和 num2 中数字的索引。

将部分乘积添加到数组中的当前值，并考虑向下一个位置进位。

步骤 5：处理进位：添加部分乘积后，确定进位（和除以 10）和余数（和模 10）。将余数存储在结果数组的当前位置，并将进位添加到下一个较高位置。

步骤 6：构建结果字符串：从左到右遍历结果数组并构建最终结果字符串。在此过程中跳过前导零。如果跳过前导零后结果字符串为空，则返回 "0"。

步骤 6.1：遍历结果数组：将所有部分乘积和进位添加到结果数组后，从最左边的位置开始遍历数组。将数组中的每个数字转换为最终结果字符串。跳过任何前导零，以确保字符串表示正确的乘积。

步骤 7：返回结果：处理完结果数组并删除前导零后，将剩余的数字转换为字符串。此字符串表示两个输入字符串的最终乘积。如果删除零后结果字符串为空，则返回 "0" 以处理零乘积的情况。

让我们在 Java 程序中实现上述方法。

文件名：StringMultiplication.java

输出

 
5535   

复杂度分析

时间复杂度

此算法的时间复杂度为 O(n1 * n2)，其中 n1 和 n2 是两个字符串的长度。这是因为第一个字符串中的每个数字都与第二个字符串中的每个数字相乘，从而产生 嵌套循环 结构。

空间复杂度

此算法的空间复杂度为 O(n1 + n2)，其中 n1 和 n2 是两个字符串的长度。这是由用于存储中间结果的整数数组产生的，该数组的最大大小为 n1 + n2，以便容纳最大可能的乘积。

方法 2：使用分治法

步骤 1：基本情况（小数字）：如果数字很小（例如，个位数），则直接相乘。这是最简单的情况，不需要完整的算法。

步骤 1.1：基本情况检查：当涉及的数字非常小，通常是一位数时，我们会跳过递归乘法过程，直接将它们相乘。例如，将 "3" 和 "5" 相乘将直接得到 "15"。这避免了不必要的复杂性，并加快了对小输入的处理速度。

步骤 2：拆分数字：对于较大的数字，将每个数字拆分成两部分。例如，如果要将 "1234" 和 "5678" 相乘

"1234" 拆分为两部分：high1 = "12" 和 low1 = "34"。

"5678" 拆分为两部分：high2 = "56" 和 low2 = "78"。

步骤 3：递归乘法：现在，我们需要计算三个较小的乘法

将高位部分相乘：high1 * high2（即，12 * 56）。

将低位部分相乘：low1 * low2（即，34 * 78）。

将每个数字的高位和低位部分之和相乘：（high1 + low1）*（high2 + low2）（即，（12 + 34）*（56 + 78））。

步骤 4：合并结果：计算三个乘积后，将它们合并以获得最终结果

第一个乘积（high1 * high2）左移两位（类似于乘以 100）。

第二个乘积（（high1 + low1）*（high2 + low2））通过减去第一个和第三个乘积并左移一位（类似于乘以 10）进行调整。

最后，直接加上第三个乘积（low1 * low2）。这比传统方法更有效地进行乘法。

步骤 4.1：移位并合并乘积：计算三个乘积后，我们需要将它们合并到最终结果中。第一个乘积（high1 * high2）左移两位，实际上乘以 100。第二个乘积代表高位和低位部分的交叉乘积，通过减去第一个和第三个乘积进行调整，然后左移一位。这确保了每个乘积在最终结果中的正确位置。

步骤 5：最终结果：合并结果后，您将获得最终的乘积。如果存在任何前导零，则将其删除以获得正确答案。

步骤 6：构建结果字符串：计算并合并所有部分乘积后，下一步是构建最终结果字符串。您首先遍历结果数组，从最左边的数字开始。在形成字符串时，请务必跳过任何前导零。如果跳过零后字符串为空，则返回 "0" 以处理结果为零的情况。

让我们在 Java 程序中实现上述方法。

文件名：KaratsubaMultiplication.java

输出

 
5453149   

复杂度分析

时间复杂度

Karatsuba 算法通过将问题分解为更小的部分来改进乘法。与执行传统乘法 O(n^2) 的操作不同，它将复杂度降低到 O(^1.585 )。这意味着 Karatsuba 可以更快地乘以大数，因为它对相同大小的输入需要更少的步骤。

空间复杂度

程序的空间复杂度为 O(n)，其中 n 是输入数字的位数。这是因为算法只需要存储中间结果和递归调用的空间，这些空间会随着输入数字的大小呈线性增长。