algoadvance

Leetcode 1880. Check if Word Equals Summation of Two Words

Problem Statement

You are given three strings firstWord, secondWord, and targetWord, each consisting of lowercase English letters.

You need to determine if the summation of the numeric values of firstWord and secondWord equals the numeric value of targetWord.

The numeric value of a word is defined by concatenating the differences between each letter and ‘a’. For instance, the numeric value of “acb” is defined as “021”, representing the concatenation of 0 for ‘a’, 2 for ‘c’, and 1 for ‘b’.

Clarifying Questions

1. Input Constraints: Are there any constraints on the lengths of firstWord, secondWord, and targetWord?
   • All given strings are of length between 1 and 8.
2. Character Set: Can we assume all characters in the strings are valid lowercase English letters?
   • Yes.
3. Output: Should the function return a boolean value?
   • Yes, it should return true if the numeric value of firstWord + secondWord equals the numeric value of targetWord, otherwise false.

Strategy

1. Convert Word to Numeric Value:
   • Write a helper function to convert a given word to its numeric value by computing the difference between each character and ‘a’, and then concatenating these differences.
2. Compare the Summation:
   • Convert firstWord, secondWord, and targetWord to their respective numeric values.
   • Convert the resulting numeric strings to integers to perform the summation and comparison.

Code

#include <iostream>
#include <string>

using namespace std;

class Solution {
public:
    bool isSumEqual(string firstWord, string secondWord, string targetWord) {
        int num1 = convertToNumericValue(firstWord);
        int num2 = convertToNumericValue(secondWord);
        int targetNum = convertToNumericValue(targetWord);
        return (num1 + num2) == targetNum;
    }
    
private:
    int convertToNumericValue(const string& word) {
        int numericValue = 0;
        for (char c : word) {
            numericValue = numericValue * 10 + (c - 'a');
        }
        return numericValue;
    }
};

int main() {
    Solution solution;
    cout << boolalpha << solution.isSumEqual("acb", "cba", "cdb") << endl; // Output: true
    cout << boolalpha << solution.isSumEqual("aaa", "a", "aab") << endl; // Output: false
    cout << boolalpha << solution.isSumEqual("aaa", "a", "aaaa") << endl; // Output: true
    return 0;
}

Time Complexity

• Conversion: Each string conversion has a time complexity of O(n), where n is the length of the string (maximum length is 8).
• Overall: The overall time complexity of the function isSumEqual is O(n), as it requires converting each of the three strings, ultimately leading to a constant time complexity given the maximum input length.

Space Complexity

• The space complexity is O(1) as no additional data structures requiring space proportional to input size are used outside the integer space for storing numeric values.

This solution efficiently addresses the problem using string manipulation and integer arithmetic constrained by given inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?