Wednesday, July 8, 2015

Leetcode 58: 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.

题目关键是要求出每一个word的 长度,一个word里面没有空格,可以使用slow 和fast两个指针来确定一个word,每次碰到一个word就更新长度,直到扫描到string的最后。碰到一个word的条件: fast - slow > 0 这样才能更新len

solution 1: 
class Solution {
public:
    int lengthOfLastWord(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        int slow = 0;
        int fast = 0;
        int len = 0;
        s += " ";
        //everytime when meet a word, update the len of the word
        for (; fast < s.size(); fast++) {
            if (s[fast] == ' ') {
                if (fast - slow > 0) len = fast-slow; //update len if meet a word
                slow = fast + 1;
            }
        }
        return len;
    }
};

solution 2:

class Solution {
public:
    int lengthOfLastWord(string s) {
        //sanity check
        if (s.size() == 0) return 0;
        int slow = 0;
        int fast = 0;
        int len = 0;
        //everytime when meet a word, update the len of the word
        for (; fast < s.size(); fast++) {
            if (s[fast] == ' ') {
                slow = fast + 1;
            } else {
                len = fast - slow + 1;
            }
        }
        return len;
    }
};
solution1 是当碰到一个可能单词的时候更新len,标志是fast走到了一个空格,但是这样做前提必须在原string后面加上”“,以防止最后一个word不能检测出来。
solution2 是每次fast 和slow相差>0时更新len,此时可能fast 和 slow之间并不是一个word,但是通过每次更新可以将所有word的长度找出来,这种方法是不需要对原字符串进行处理的。所有solution2效率更高。
slow 和 fast指针处理的题目可能有很多种途径得到solution,但是有些solution就很简单高效。

No comments:

Post a Comment