Friday, September 12, 2014

Leetcode: Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.
If the last word does not exist, return 0.
Note: A word is defined as a character sequence consists of non-space characters only.
For example,
Given s = "Hello World",
return 5.
Understand the problem:
The problem gives a string s consists of upper/lower-case alphabets and empty space characters, return the length of the last word in the string. If the last word does not exist, return 0. Note that a word is defined as a character sequence consist of non-space characters only.  Several cases need to think about.

  • For empty string "", return 0;
  • For string with one word, return the length of the word
  • For string with trailing empty spaces, e.g. "Hello World     ", return the length of the last word, ie. World, which is 5.
  • For string with leading empty spaces, e.g. "    Hello World", it does not matter since we only wanna the length of the last word.

Solution:
The easiest way we can use is to apply the Java regular expression, where we use the split method. 

Code (Java):
public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        String delim = "[ ]+";
        String[] strs = s.split(delim);
        int length = 0;
        
        if (strs.length == 0) {
            return 0;
        } else {
            length = strs[strs.length - 1].length();
        }
        
        return length;
    }
}

A naive solution:
What if we are not allowed to use the Java split() method, can we manually solve this question without using any advanced language features? The answer is yes. We use two pointers, i, and j, starting from the end of the string. j points to the end of the word, while traverse the string in reverse order until reach to an empty space. Then the length of the last word is j - i. Be careful about the trailing spaces in the string.

Code (Java):
public class Solution {
    public int lengthOfLastWord(String s) {
        if (s == null || s.length() ==0) {
            return 0;
        }
        
        int end = s.length() - 1;
        // jump trailing empty spaces
        while (end >= 0 && s.charAt(end) == ' ') {
            end--;
        }
        
        int start = end;
        
        while (start >= 0 && s.charAt(start) != ' ') {
            start--;
        }
        
        return end - start;
    }
}






1 comment:

  1. There is shocking news in the sports betting industry.

    It has been said that every bettor must watch this,

    Watch this or stop placing bets on sports...

    Sports Cash System - Advanced Sports Betting Software.

    ReplyDelete