Solution by ccwei


  • 1
    C

    Approach #1 Naive approach [Accepted]

    Intuition

    From the problem description we can see that there are three rules to check, we could simply follow the description of the rules and make sure the input matches at least one of the rules.

    Algorithm

    C#

    public class Solution {
        public bool DetectCapitalUse(string word) {
            // Check if it matches the first rule, all letters should be capitals
            bool matchFirstRule = true;
            for(int i = 0; i < word.Length; i++) {
                if(!char.IsUpper(word[i])) {
                    matchFirstRule = false;
                    break;
                }
            }
            
            // Check if it matches the second rule, all letters should not be capitals
            bool matchSecondRule = true;
            for(int i = 0; i < word.Length; i++) {
                if(!char.IsLower(word[i])) {
                    matchSecondRule = false;
                }
            }
            
            // Check if it matches the third rule, only first character should be capital
            bool matchThirdRule = true;
            bool firstCap = false;
            for(int i = 0; i < word.Length; i++) {
                if(i == 0) {
                    firstCap = char.IsUpper(word[i]);
                    continue;
                }
                
                if(!firstCap || char.IsUpper(word[i])) {
                    matchThirdRule = false;
                    break;
                }
            }
            
            // Returns true as long as it matches one of the rules, otherwise false
            return matchFirstRule || matchSecondRule || matchThirdRule;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(3n) = O(n)$$.

      We loop through the input 3 times, one for each rule.

    • Space complexity : $$O(1)$$. We only create constant number of booleans.


    Approach #2 Object Oriented approach [Accepted]

    Algorithm

    In Approach#1, the code is hard to read and maintain, espeically if problem is changed to include more rules. We could improve it by seperating out the rules into different classes, and loop through them to validate against all the rules.

    C#

    public class Solution {
        public bool DetectCapitalUse(string word) {
            var rules = new IRule[] {
                new AllCapRule(),
                new AllLowerRule(),
                new FirstCapRule()
            };
            
            bool result = false;
            for(int i = 0; i < rules.Length; i++) {
                result = result || rules[i].Validate(word);
            }
            
            return result;
        }
    }
    
    // Create an interface so tat we can call the same method to validate all rules
    public interface IRule {
        bool Validate(string input);
    }
    
    public class AllCapRule: IRule {
        public bool Validate(string input) {
            for(int i = 0; i < input.Length; i++) {
                if(!char.IsUpper(input[i])) {
                    return false;
                }
            }
            
            return true;
        }
    }
    
    public class AllLowerRule: IRule {
        public bool Validate(string input) {
            for(int i = 0; i < input.Length; i++) {
                if(!char.IsLower(input[i])) {
                    return false;
                }
            }
            
            return true;
        }
    }
    
    public class FirstCapRule: IRule {
        public bool Validate(string input) {
            bool firstCap = false;
            for(int i = 0; i < input.Length; i++) {
                if(i == 0) {
                    firstCap = char.IsUpper(input[i]);
                    continue;
                }
                
                if(!firstCap || char.IsUpper(input[i])) {
                    return false;
                }
            }
            
            return true;
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(3n) = O(n)$$.

    • Space complexity : $$O(1)$$.

    Analysis is the same as Approach #1.


    Approach #3 Counting Capitals [Accepted]

    Algorithm

    Instead of validating against three rules and loop through the input indivisually, we could count the number of capitals once and use it to see if they matches one of the rules.

    Here is how we can use capitals count to see if they matches each of the rules.

    1. Capitals counts euqals to string length
    2. Capitals counts equals 0
    3. Capitals counts is 1, and the first character is capital

    C#

    public class Solution {
        public bool DetectCapitalUse(string word) {
            int capitalCount = 0;
            for(int i = 0; i < word.Length; i++) {
                if(char.IsUpper(word[i])) {
                    capitalCount++;
                }
            }
           
            return capitalCount == word.Length || 
                capitalCount == 0 || 
                (capitalCount == 1 && char.IsUpper(word[0]));
        }
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    • Space complexity : $$O(1)$$.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.