Last active
October 5, 2023 12:29
-
-
Save alvinlau/37a524d5d589b780761369177dbcaa56 to your computer and use it in GitHub Desktop.
43. Multiply Strings
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # https://leetcode.com/problems/multiply-strings/ | |
| # 43. Multiply String | |
| # Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. | |
| # Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. | |
| # Example 1: | |
| # Input: num1 = "2", num2 = "3" | |
| # Output: "6" | |
| # Example 2: | |
| # Input: num1 = "123", num2 = "456" | |
| # Output: "56088" | |
| # Constraints: | |
| # 1 <= num1.length, num2.length <= 200 | |
| # num1 and num2 consist of digits only. | |
| # Both num1 and num2 do not contain any leading zero, except the number 0 itself. | |
| # @param {String} num_str1 | |
| # @param {String} num_str2 | |
| # @return {String} | |
| def multiply(num_str1, num_str2) | |
| return '0' if (num_str1 == '0' || num_str2 == '0') | |
| digits1 = digits num_str1 | |
| digits2 = digits num_str2 | |
| # array product of all the digits ready to be multiplied | |
| multiples = digits1.product(digits2) | |
| # multiplied products sorted by power, e.g. 69 at 10^2 | |
| subtotals = [] | |
| multiples.each do |pair| | |
| value = pair[0][:value] * pair[1][:value] | |
| power = pair[0][:power] + pair[1][:power] | |
| subtotals[power] ||= 0 | |
| subtotals[power] += value | |
| end | |
| # assemble the final result in string form | |
| result = Array.new(num_str1.size + num_str2.size) | |
| carry = 0 | |
| subtotals.each_with_index do |value, power| | |
| sum = value + carry | |
| result[power] = sum % 10 | |
| carry = (sum > 9) ? (sum / 10) : 0 | |
| end | |
| result[subtotals.size] = carry if carry > 0 | |
| result.compact! | |
| return result.reverse.join.sub!(/^0*/, '') | |
| # old solution that just multiplies both numbers | |
| # int1 = toInt(num_str1) | |
| # int2 = toInt(num_str2) | |
| # (int1 * int2).to_s | |
| end | |
| def digits(num_str) | |
| digits = num_str.reverse.each_char.with_index.map do |value, power| | |
| {value: value.to_i, power:} | |
| end | |
| end | |
| # converting each char to int using to_i is not that much more than writing out a case table | |
| # or using the asci value for the char, that's probably what to_i does somewhere anyway | |
| def toInt(num_str) | |
| sum = 0 | |
| digits = num_str.reverse.each_char.map(&:to_i) | |
| digits.each_with_index do |digit, i| | |
| sum += digit * (10 ** i) | |
| end | |
| sum | |
| end | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment