Leetcode 1880: Check if Word Equals Summation of Two Words
You are given three strings: ‘firstWord’, ‘secondWord’, and ’targetWord’. Each string contains only lowercase English letters from ‘a’ to ‘j’. The value of each letter corresponds to its position in the alphabet starting from ‘a’ as 0 (‘a’ -> 0, ‘b’ -> 1, …, ‘j’ -> 9). The value of a string is the concatenation of the values of its letters, which is then interpreted as an integer. Your task is to check if the sum of the values of ‘firstWord’ and ‘secondWord’ equals the value of ’targetWord’. Return true if it does, and false otherwise.
Problem
Approach
Steps
Complexity
Input: You are given three strings 'firstWord', 'secondWord', and 'targetWord'. Each string consists of lowercase letters from 'a' to 'j'.
Example: firstWord = 'acb', secondWord = 'cba', targetWord = 'cdb'
Constraints:
• 1 <= firstWord.length, secondWord.length, targetWord.length <= 8
• firstWord, secondWord, and targetWord consist of lowercase English letters from 'a' to 'j' inclusive.
Output: Return true if the sum of the numerical values of 'firstWord' and 'secondWord' equals the numerical value of 'targetWord'. Otherwise, return false.
Example: true
Constraints:
Goal: Convert each word to its numerical value and check if the sum of the values of 'firstWord' and 'secondWord' equals 'targetWord'.
Steps:
• For each word, convert each character to its corresponding value and concatenate them to form an integer.
• Check if the sum of the first and second word values equals the target word value.
Goal: The given strings consist of lowercase letters from 'a' to 'j'. The lengths of the strings are between 1 and 8.
Steps:
• The length of each string is between 1 and 8.
• Each character in the strings is between 'a' and 'j'.
Assumptions:
• The input strings contain only lowercase English letters from 'a' to 'j'.
• The values of the words are formed by concatenating the positions of the characters in the alphabet.
• Input: Example 1: firstWord = 'acb', secondWord = 'cba', targetWord = 'cdb'
• Explanation: The numerical value of 'acb' is 21, the value of 'cba' is 210, and the value of 'cdb' is 231. The sum of 21 and 210 equals 231, so the result is true.
• Input: Example 2: firstWord = 'aaa', secondWord = 'a', targetWord = 'aab'
• Explanation: The numerical value of 'aaa' is 0, the value of 'a' is 0, and the value of 'aab' is 1. The sum of 0 and 0 does not equal 1, so the result is false.
• Input: Example 3: firstWord = 'aaa', secondWord = 'a', targetWord = 'aaaa'
• Explanation: The numerical value of 'aaa' is 0, the value of 'a' is 0, and the value of 'aaaa' is 0. The sum of 0 and 0 equals 0, so the result is true.
Approach: Convert each word to its numerical value by iterating over each character and using its position in the alphabet to form the corresponding number. Then, compare the sum of the first two words' values with the value of the target word.
Observations:
• Each word can be transformed into an integer by processing each letter and using its alphabetical value.
• The solution requires simple arithmetic comparison after converting the words to their numerical values.
• This approach works efficiently given the constraints, as the maximum length of the strings is 8.
Steps:
• Loop through each word and for each character, subtract 'a' from it to get its position in the alphabet.
• Concatenate the results to form the full number for each word.
• Sum the first two words' values and compare with the third word's value.
Empty Inputs:
• The input will never be empty, as the length is guaranteed to be at least 1.
Large Inputs:
• Input strings will be of length at most 8, which ensures the operations are fast.
Special Values:
• If all words are 'a', the sum will be 0.
Constraints:
• Handle cases where the sum of two words equals or does not equal the third word.
bool isSumEqual(string firstWord, string secondWord, string targetWord) {
int first=0,second=0,target=0;
for(int i=0;i<firstWord.size();i++)
first=first*10 + (firstWord[i]-'a');
for(int i=0;i<secondWord.size();i++)
second=second*10 +(secondWord[i]-'a');
for(int i=0;i<targetWord.size();i++)
target=target*10 +(targetWord[i]-'a');
return first+second == target;
}
1 : Function Definition
bool isSumEqual(string firstWord, string secondWord, string targetWord) {
Defines a function to check if the sum of two word-based integers equals the third.
2 : Variable Initialization
int first=0,second=0,target=0;
Initializes integers to store numerical representations of the input strings.
3 : Loop and Conversion
for(int i=0;i<firstWord.size();i++)
Iterates through the firstWord to convert it into a numeric value.
4 : Conversion
first=first*10 + (firstWord[i]-'a');
Converts each character of firstWord into a digit and appends it to the numeric value.
5 : Loop and Conversion
for(int i=0;i<secondWord.size();i++)
Iterates through the secondWord to convert it into a numeric value.
6 : Conversion
second=second*10 +(secondWord[i]-'a');
Converts each character of secondWord into a digit and appends it to the numeric value.
7 : Loop and Conversion
for(int i=0;i<targetWord.size();i++)
Iterates through the targetWord to convert it into a numeric value.
8 : Conversion
target=target*10 +(targetWord[i]-'a');
Converts each character of targetWord into a digit and appends it to the numeric value.
9 : Validation
return first+second == target;
Checks if the sum of the first and second integers equals the target integer.
Best Case: O(n), where n is the length of the longest string.
Average Case: O(n), where n is the length of the longest string.
Worst Case: O(n), where n is the length of the longest string.
Description: In the worst case, we iterate over each string once, processing each character.
Best Case: O(1), as no extra space is needed apart from storing intermediate results.
Worst Case: O(1), as we use a constant amount of extra space.
Description: The space complexity is constant since we only need to store a few integer variables.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus