grid47 Exploring patterns and algorithms
Sep 16, 2024
4 min read
Solution to LeetCode 520: Detect Capital Problem
We define the correct usage of capital letters in a word as either all letters being capitalized, all letters being lowercase, or only the first letter being capitalized while the rest are lowercase. Given a string word, return true if the word follows one of these patterns, and false otherwise.
Problem
Approach
Steps
Complexity
Input: The input consists of a string `word` which is composed of English alphabet letters.
Example: word = 'HELLO'
Constraints:
• 1 <= word.length <= 100
• The word contains only uppercase and lowercase English letters.
Output: Return true if the capital usage in the word is correct, otherwise return false.
Example: true, false
Constraints:
• The output should be a boolean indicating whether the word follows the correct capitalization rules.
Goal: Check if the capitalization pattern of the word matches one of the valid patterns.
Steps:
• 1. Check if the word is completely uppercase.
• 2. Check if the word is completely lowercase.
• 3. Check if only the first letter is uppercase and the rest are lowercase.
Goal: The constraints for input and output of the problem.
Steps:
• 1 <= word.length <= 100
• The word contains only lowercase and uppercase English letters.
Assumptions:
• The word contains only English alphabet characters.
• The length of the word is between 1 and 100 characters.
• Input: word = 'HELLO'
• Explanation: The word is all in uppercase, which is valid.
• Input: word = 'FlaG'
• Explanation: The word has an incorrect capitalization pattern (only the first letter is uppercase and the rest are lowercase), which is invalid.
Approach: The approach is to verify the capitalization pattern of the word by checking each of the possible valid patterns.
Observations:
• We need to check the word against the three valid capitalization patterns.
• A simple check on the word can verify the capitalization pattern.
Steps:
• 1. Check if all characters in the word are uppercase.
• 2. Check if all characters in the word are lowercase.
• 3. Check if only the first character is uppercase and all other characters are lowercase.
Empty Inputs:
• If the word length is 1, it is always valid since a single character is either uppercase or lowercase.
Large Inputs:
• The algorithm must handle words of length up to 100 efficiently.
Special Values:
• All uppercase or all lowercase words should always return true.
Constraints:
• Ensure the algorithm efficiently handles all inputs within the constraints.
This defines the `detectCapitalUse` function that checks the capitalization of a given word.
2 : Loop
for(int i =1; i < word.size(); i++) {
A loop starts at index 1 to iterate through each character of the word, starting from the second character.
3 : Condition Check
if(isupper(word[1]) != isupper(word[i]) ||
Check if the current character's case (upper or lower) matches the second character's case. If not, or if it violates other capitalization rules, return false.
4 : Condition Check
islower(word[0]) && isupper(word[i]))
Additionally, check if the first character is lowercase while a later character is uppercase, which would be an invalid capitalization pattern.
5 : Return False
returnfalse;
If any capitalization rules are violated, return false immediately.
6 : Return True
returntrue;
If all checks pass without returning false, return true, meaning the capitalization use is correct.
Best Case: O(n) where n is the length of the word.
Average Case: O(n) where n is the length of the word.
Worst Case: O(n) where n is the length of the word.
Description: The time complexity is O(n) because we only need to check the word once.
Best Case: O(1), no additional space required.
Worst Case: O(1), since we only need a constant amount of space.
Description: The space complexity is O(1) because we do not need any additional space beyond the input.
