Java O(n) Easy To Understand Solution


  • 1
    B

    Explanation
    There are many ways to approach this problem that will run in O(n), but my solution simply scans through each character in the string word only once.

    The idea is to first figure out the number of capitalized characters within word. Then, with this newfound number, we use the fact that the 3 valid cases are easy to check for. See code below.

    Time Complexity
    The time complexity is O(n) where n is the number of characters in input word, since we iterate through them to compute the number of capitalized characters.

    class Solution {
        public int getNumCapitals(String word) {
            int result = 0;
            for (int i = 0; i < word.length(); i++) {
                if (word.charAt(i) >= 'A' && word.charAt(i) <= 'Z') {
                    result++;
                }
            }
            return result;
        }
        
        public boolean detectCapitalUse(String word) {
            int numCapitals = getNumCapitals(word);
            // Case 1: All letters are capitals
            if (numCapitals == word.length()) {
                return true;
            } 
            // Case 2: No letters are capitals
            else if (numCapitals == 0) {
                return true;
            }
            // Case 3: First letter capitalized
            else if (numCapitals == 1 && word.charAt(0) >= 'A' 
                                      && word.charAt(0) <= 'Z') {
                return true;
            }
            return false;
        }
    }
    

  • 1
    G

    Very clean code. +1


Log in to reply
 

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