leet_rs/
multiply_strings.rs

1pub struct MultiplyStringsSolution {}
2
3impl MultiplyStringsSolution {
4    /// Adds the product of two digits to a slice of digits representing a larger number.
5    ///
6    /// # Arguments
7    /// * `res` -  A mutable reference to a slice of digits representing a larger number.
8    /// * `index` -  The index in `res` where the product should be added.
9    /// * `product` -  The product of two digits.
10    ///
11    /// # Returns
12    /// None
13    ///
14    /// # Examples
15    ///
16    /// ```
17    /// use leet_rs::multiply_strings::MultiplyStringsSolution;
18    /// let mut res = vec![0, 0, 0];
19    /// MultiplyStringsSolution::add_product(&mut res, 1, 6);
20    /// assert_eq!(res, vec![0, 6, 0]);
21    /// ```
22    ///
23    /// # Complexity
24    ///
25    /// # Time complexity
26    /// O(1)
27    ///
28    /// # Space complexity
29    /// O(1)
30    pub fn add_product(res: &mut [u8], index: usize, product: u8) {
31        let sum = res[index] + product;
32        // Update the current digit and carry the overflow to the next digit
33        res[index] = sum % 10;
34        let carry = sum / 10;
35        if carry > 0 {
36            // Carry the overflow to the next digit
37            res[index - 1] += carry;
38        }
39    }
40
41    /// Multiplies two strings representing non-negative integers and returns their product as a string.
42    ///
43    /// # Arguments
44    /// * `num1` -  The first number to multiply.
45    /// * `num2` -  The second number to multiply.
46    ///
47    /// # Returns
48    /// A string representing the product of `num1` and `num2`.
49    ///
50    /// # Examples
51    ///
52    /// ```
53    /// use leet_rs::multiply_strings::MultiplyStringsSolution;
54    /// let num1 = "123".to_string();
55    /// let num2 = "456".to_string();
56    /// let product = MultiplyStringsSolution::multiply(num1, num2);
57    /// assert_eq!(product, "56088".to_string());
58    /// ```
59    ///
60    /// # Complexity
61    ///
62    /// # Time complexity
63    /// O(mn), where m and n are the lengths of `num1` and `num2`, respectively.
64    ///
65    /// # Space complexity
66    /// O(m + n)
67    pub fn multiply(num1: String, num2: String) -> String {
68        // Convert input strings to byte arrays for faster access
69        let n1 = num1.as_bytes();
70        let n2 = num2.as_bytes();
71
72        // Get lengths of input byte arrays
73        let len1 = n1.len();
74        let len2 = n2.len();
75
76        // Initialize result vector with 0s
77        let mut res = vec![0; len1 + len2];
78
79        // Iterate over each digit of the first number from right to left
80        for i in (0..len1).rev() {
81            // Get the current digit of the first number
82            let a = n1[i] - b'0';
83
84            // Iterate over each digit of the second number from right to left
85            for j in (0..len2).rev() {
86                // Get the current digit of the second number
87                let b = n2[j] - b'0';
88
89                // Calculate the product of the two digits
90                let product = a * b;
91
92                // Add the product to the current digit of the result vector
93                Self::add_product(&mut res, i + j + 1, product);
94            }
95        }
96
97        // Remove any leading zeroes from the result vector
98        while res.len() > 1 && res[0] == 0 {
99            res.remove(0);
100        }
101
102        // Convert the result vector back to a string and return it
103        String::from_utf8(res.iter().map(|&x| x + b'0').collect()).unwrap()
104    }
105}
leet_rs/multiply_strings.rs

leet_rs/
multiply_strings.rs
