Leetcode – Check if Word Equals Summation of Two Words Solution

Spread the love

The “Check if Word Equals Summation of Two Words” is a coding challenge often encountered on LeetCode. It exemplifies problems involving string manipulation, arithmetic operations, and simple logic to determine whether a condition is met. It provides a fun twist on word problems and offers learners an opportunity to think creatively about how words and numbers can interact in programming.

Let’s break down the problem, understand its constraints and requirements, and then walk through different solutions.

Problem Statement

The problem states that each letter in the word is assigned a unique number from 'a' to 'z' – 0 to 25 respectively. You are given three strings firstWord, secondWord, and targetWord. You need to check if the summation of the numerical values of the firstWord and secondWord is equal to the numerical value of the targetWord.

Example

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" -> "201" -> 201.
Thus, 21 + 210 = 201 which equals the numerical value of targetWord.

Brute-Force Approach

One straightforward method to solve this problem is to:

  1. Convert each word to its respective numerical value.
  2. Sum the values of the first two words.
  3. Check if the sum equals the value of the targetWord.

Python code for this approach:

def isSumEqual(firstWord: str, secondWord: str, targetWord: str) -> bool:
    def word_to_num(word: str) -> int:
        return int(''.join(str(ord(c) - ord('a')) for c in word))
    
    return word_to_num(firstWord) + word_to_num(secondWord) == word_to_num(targetWord)

Time Complexity: O(n)

Where n is the maximum length among the three words. The reason is that we iterate through each word once, converting it to its numerical value.

Space Complexity: O(n)

The converted numerical string can be as long as the input word.

Optimized Approach

Given the constraints, the brute force approach is efficient enough. However, you could slightly optimize the space by directly calculating the numerical values without explicitly forming the intermediate numerical string.

Python Code:

def isSumEqual(firstWord: str, secondWord: str, targetWord: str) -> bool:
    def word_to_num(word: str) -> int:
        num = 0
        for c in word:
            num = num * 10 + (ord(c) - ord('a'))
        return num
    
    return word_to_num(firstWord) + word_to_num(secondWord) == word_to_num(targetWord)

In this method, we use arithmetic operations to derive the numerical value, bypassing the need for an intermediate string representation.

Time Complexity: O(n)

The time complexity remains the same because we’re still iterating over each character in the words once.

Space Complexity: O(1)

We’re now only using a constant amount of extra space (the integer variable num), making the space complexity O(1).

Conclusion

The “Check if Word Equals Summation of Two Words” problem is a fantastic introductory problem that allows individuals to practice string manipulation, arithmetic operations, and character-to-number conversions in Python. Although it doesn’t require advanced algorithms or data structures, it emphasizes the importance of understanding problem statements and thinking through solutions.

Leave a Reply