Teaching Kids Programming – Check if Word Equals Summation of Two Words

Teaching Kids Programming: Videos on Data Structures and Algorithms

The letter value of a letter is its position in the alphabet starting from 0 (i.e. ‘a’ -> 0, ‘b’ -> 1, ‘c’ -> 2, etc.).

The numerical value of some string of lowercase English letters s is the concatenation of the letter values of each letter in s, which is then converted into an integer.

For example, if s = “acb”, we concatenate each letter’s letter value, resulting in “021”. After converting it, we get 21.
You are given three strings firstWord, secondWord, and targetWord, each consisting of lowercase English letters ‘a’ through ‘j’ inclusive.

Return true if the summation of the numerical values of firstWord and secondWord equals the numerical value of targetWord, or false otherwise.

Example 1:
Input: firstWord = “acb”, secondWord = “cba”, targetWord = “cdb”
Output: true
Explanation:
The numerical value of firstWord is “acb” -> “021” -> 21.
The numerical value of secondWord is “cba” -> “210” -> 210.
The numerical value of targetWord is “cdb” -> “231” -> 231.
We return true because 21 + 210 == 231.

Example 2:
Input: firstWord = “aaa”, secondWord = “a”, targetWord = “aab”
Output: false
Explanation:
The numerical value of firstWord is “aaa” -> “000” -> 0.
The numerical value of secondWord is “a” -> “0” -> 0.
The numerical value of targetWord is “aab” -> “001” -> 1.
We return false because 0 + 0 != 1.

Example 3:
Input: firstWord = “aaa”, secondWord = “a”, targetWord = “aaaa”
Output: true
Explanation:
The numerical value of firstWord is “aaa” -> “000” -> 0.
The numerical value of secondWord is “a” -> “0” -> 0.
The numerical value of targetWord is “aaaa” -> “0000” -> 0.
We return true because 0 + 0 == 0.

Constraints:
1 <= firstWord.length, secondWord.length, targetWord.length <= 8
firstWord, secondWord, and targetWord consist of lowercase English letters from ‘a’ to ‘j’ inclusive.

Hints:
Convert each character of each word to its numerical value.
Check if the numerical values satisfies the condition.

Convert Letters to Numbers

We can construct the numerical string by the mapping, and then convert it back to base 10 integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:        
        def f(s):
            g = {
                'a': 0,
                'b': 1,
                'c': 2,
                'd': 3,
                'e': 4,
                'f': 5,
                'g': 6,
                'h': 7,
                'i': 8,
                'j': 9
            }
            a = ""
            for i in s:
                a += str(g[i])
            return int(a)
        return f(firstWord) + f(secondWord) == f(targetWord)

class Solution:
    def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:        
        def f(s):
            g = {
                'a': 0,
                'b': 1,
                'c': 2,
                'd': 3,
                'e': 4,
                'f': 5,
                'g': 6,
                'h': 7,
                'i': 8,
                'j': 9
            }
            a = ""
            for i in s:
                a += str(g[i])
            return int(a)
        return f(firstWord) + f(secondWord) == f(targetWord)

Time complexity is O(N) and space complexity is O(N) as we keep the new numerical string. N is the number of the characters in the original words.

Alternatively, we can go through each character and update the decimal value along the way as we are converting to base 10:

1
2
3
4
5
6
7
8

class Solution:
    def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:
        def f(s):
            a = 0
            for i in s:
                a = a * 10 + ord(i) - 97
            return a
        return f(firstWord) + f(secondWord) == f(targetWord)

class Solution:
    def isSumEqual(self, firstWord: str, secondWord: str, targetWord: str) -> bool:
        def f(s):
            a = 0
            for i in s:
                a = a * 10 + ord(i) - 97
            return a
        return f(firstWord) + f(secondWord) == f(targetWord)

Time complexity is O(N) and space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —