1880. Check if Word Equals Summation of Two Words

EasyString

Problem Description

The problem presents a scenario in which each letter from 'a' to 'j' has an associated numeric value based on its position in the English alphabet, starting with 'a' as 0 through 'j' as 9. This conversion applies a positional numbering system where each character has a place value that is a power of 10 based on its position in the string (similar to decimal numbers). Given three lowercase strings firstWord, secondWord, and targetWord, the task is to determine whether the sum of the numeric values of firstWord and secondWord is equal to the numeric value of targetWord.

To illustrate:

Suppose firstWord is "abc" which converts to numerical value as "012" => 12 in integer.
Suppose secondWord is "de" which converts to numerical value as "34" => 34 in integer.
Suppose targetWord is "fg" which converts to numerical value as "56" => 56 in integer.

One would then check if 12 (firstWord) + 34 (secondWord) equals 56 (targetWord), and based on this, return true or false.

Intuition

The solution hinges on converting each string into its corresponding numeric value and then comparing the sum of the numeric values of firstWord and secondWord with the numeric value of targetWord. This involves understanding the positional value of each letter, akin to how positional value works in numerical digits.

By defining a function f(s) which converts a given string s into its numeric equivalent, we can simplify the problem into three conversions followed by a numeric comparison. The function takes the following steps for each character in the string:

It subtracts the ASCII value of 'a' from the ASCII value of the character to find the numeric value of the letter (as 'a' maps to 0, 'b' maps to 1, and so on).
It multiplies the current result by 10 (since we're moving one place to the left in a positional number system) and adds the numeric value of the letter.

This conversion function is then applied to each word, and the results are added for firstWord and secondWord. The final step is to verify if this sum equals the numeric value of targetWord.

Solution Approach

The solution applies a simple algorithmic approach that parses each character of the input strings and converts it to a numerical value based on its position in the alphabet. No complex data structures are needed — just a fundamental loop and some basic arithmetic operations. Here's an analysis of the steps:

The helper function f(s) is designed to process a single string s and convert it into its corresponding numeric value.
- We initialize res to 0, which will serve as an accumulator for the resultant numeric value.
- For every character c in the string s, the function converts it from a letter to a number by using the expression (ord(c) - ord('a')). Here, ord(c) gives the ASCII value of character c and ord('a') gives the ASCII value of the letter 'a'. Subtracting the latter from the former yields a number from 0 to 9, corresponding to the letters 'a' to 'j'.
- The accumulator res is then updated by multiplying it by 10 (to shift its digit one place to the left) and adding the numeric value of the current character. This effectively "appends" the numeric character value to the result, mimicking the concatenation of numbers.
After defining the conversion function, the main function isSumEqual applies this helper function to each of the three input words: firstWord, secondWord, and targetWord.
- We then sum the results of firstWord and secondWord, and compare it with the result of targetWord.
- If the sum is equal to the numeric value of targetWord, the function returns True. Otherwise, it returns False.

The solution doesn't use any complex patterns or algorithms—it's a direct application of basic programming constructs such as loops and conditions along with ASCII operations to perform the task. The elegance of the solution lies in its simplicity and the realization that string manipulation can be dealt with fundamental arithmetic operations and character encoding principles.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach with three strings firstWord, secondWord, and targetWord.

Suppose we have:

firstWord as "acd" which should convert to numerical value as "023" => 23 in integer.
secondWord as "ba" which should convert to numerical value as "10" => 10 in integer.
targetWord as "cde" which should convert to numerical value as "234" => 234 in integer.

Using the algorithm described in the solution approach, let's apply these steps:

Convert firstWord ("acd") to its numeric equivalent:
- 'a' is the 0th letter, so the current result is 0.
- 'c' is the 2nd letter, so we take the current result of 0, multiply by 10 (giving 0), and add 2 to get 2.
- 'd' is the 3rd letter, so we take the current result of 2, multiply by 10 (giving 20), and add 3 to get 23.

The numeric value of firstWord is hence 23.

Convert secondWord ("ba") to its numeric equivalent:
- 'b' is the 1st letter, so the current result is 1.
- 'a' is the 0th letter, so we take the current result of 1, multiply by 10 (giving 10), and add 0 to get 10.

The numeric value of secondWord is hence 10.

Convert targetWord ("cde") to its numeric equivalent:
- 'c' is the 2nd letter, so the current result is 2.
- 'd' is the 3rd letter, so we take the current result of 2, multiply by 10 (giving 20), and add 3 to get 23.
- 'e' is the 4th letter, so we take the current result of 23, multiply by 10 (giving 230), and add 4 to get 234.

The numeric value of targetWord is hence 234.

Sum the results of firstWord and secondWord:
- The sum of 23 (firstWord) and 10 (secondWord) is 33.

Finally, we compare this sum with the numeric value of targetWord:

The sum we have is 33, which is not equal to the numeric value of targetWord, 234.

Therefore, the function would return False for this example since 33 does not equal 234. This illustrates the solution approach of converting the alphabetic string into a numerical value and then adding to compare with a third numeric string value.

Solution Implementation

1class Solution:
2    def isSumEqual(self, first_word: str, second_word: str, target_word: str) -> bool:
3        # Helper function to convert a string to a numerical value
4        # based on the position of each character in the alphabet.
5        def convert_to_number(s: str) -> int:
6            result = 0
7            for char in s:
8                # Subtract 'a' from the char to get its position in the alphabet
9                # where 'a' = 0, 'b' = 1, ..., 'j' = 9, and then shift the result
10                # left by one decimal place (multiply by 10) for each new character.
11                result = result * 10 + (ord(char) - ord('a'))
12            return result
13
14        # Check if the sum of the numerical values for first_word and second_word
15        # is equal to the numerical value of target_word.
16        return convert_to_number(first_word) + convert_to_number(second_word) == convert_to_number(target_word)
17

1class Solution {
2    // Method to determine if the numeric value of targetWord equals the sum of numeric values of firstWord and secondWord
3    public boolean isSumEqual(String firstWord, String secondWord, String targetWord) {
4        // Utilizing helper method 'convertToNumericValue' to get numeric values and checking for equality
5        return convertToNumericValue(firstWord) + convertToNumericValue(secondWord) == convertToNumericValue(targetWord);
6    }
7
8    // Helper method to convert a string where each character represents a digit from 'a' = 0 to 'j' = 9, into its numeric value
9    private int convertToNumericValue(String word) {
10        int numericValue = 0; // Initialize result to zero
11        // Iterate through the characters in the string
12        for (char character : word.toCharArray()) {
13            // Shift existing numericValue one decimal place and add the numeric equivalent of the character
14            numericValue = numericValue * 10 + (character - 'a');
15        }
16        // Return the total numeric value of the string
17        return numericValue;
18    }
19}
20

1class Solution {
2public:
3    // Function to check if the sum of numerical values of two words is equal to the numerical value of a target word
4    bool isSumEqual(string firstWord, string secondWord, string targetWord) {
5        // Check if the sum of the numerical equivalents of firstWord and secondWord is equal to that of targetWord
6        return convertToNumber(firstWord) + convertToNumber(secondWord) == convertToNumber(targetWord);
7    }
8
9    // Helper function to convert a string word to its numerical equivalent based on the problem's rule
10    // 'a' corresponds to 0, 'b' to 1, ..., 'j' to 9.
11    int convertToNumber(string word) {
12        int result = 0; // Initialize result to hold the numerical value of the word
13        // Iterate through each character of the string
14        for (char ch : word) {
15            // Multiply the current result by 10 and add the numerical equivalent of character 'ch'
16            result = result * 10 + (ch - 'a');
17        }
18        return result; // Return the final numerical value of the word
19    }
20};
21

1function isSumEqual(firstWord: string, secondWord: string, targetWord: string): boolean {
2    // Calculates the numeric value of a given string based on the problem's rules,
3    // where 'a' corresponds to 0, 'b' to 1, ... 'j' to 9.
4    const calculateStringValue = (word: string) => {
5        let value = 0; // Initialize the numeric value as 0.
6
7        // Loop through each character in the string.
8        for (const char of word) {
9            value = value * 10 + (char.charCodeAt(0) - 'a'.charCodeAt(0));
10        }
11
12        // Return the final numeric value of the string.
13        return value;
14    };
15
16    // Compare the sum of the numeric values of the first two words to the numeric value of the target word.
17    return calculateStringValue(firstWord) + calculateStringValue(secondWord) === calculateStringValue(targetWord);
18}
19

Time and Space Complexity

The given Python code defines a method isSumEqual that checks if the numerical value of the sum of two words is equal to the numerical value of a third word, considering the words are treated as base-10 numbers where 'a' corresponds to 0, 'b' to 1, up to 'j' corresponding to 9.

The time complexity of the function f is O(N), where N is the length of the input string s. This is because for each character in the string, it performs a constant number of operations (calculating the difference between the character code and the code of 'a', then multiplying the previous result by 10, and adding the numerical value of the character).

The time complexity of the overall isSumEqual function is determined by the lengths of the input strings. If we denote the lengths of firstWord, secondWord, and targetWord as N1, N2, and N3 respectively, then the total runtime is O(N1 + N2 + N3), since each word is processed individually by the function f.

As for the space complexity, the auxiliary space used by the function f is O(1), since it only uses a fixed number of integer variables, regardless of the input size. This means the space complexity of the isSumEqual function is also O(1) because it only calls f for each of the words without storing any additional information that grows with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know