LengthOfLastWord [source code]

public class LengthOfLastWord {
static
/******************************************************************************/
public class Solution {
    public int lengthOfLastWord(String s) {
        char[] chs = s.toCharArray();
        boolean inWord = false;
        int begin = chs.length;
        for (int i = chs.length - 1; i >= 0; i--) {
            if (!inWord && chs[i] == ' ') continue;
            else if (!inWord && chs[i] != ' ') {
                inWord = true;
                begin = i;
                if (i == 0) return 1;
            } else if (inWord && chs[i] == ' ') {
                return begin - i;
            } else if (inWord && i == 0) {
                return begin - i + 1;
            }
        }
        return 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LengthOfLastWord.Solution tester = new LengthOfLastWord.Solution();
        String[] inputs = {
            "a",
            "   123456    ",
            "123456",
            "",
        };
        for (String s : inputs) {
            Printer.openColor("yellow");
            System.out.print(s);
            Printer.closeColor();
            System.out.println(" -> " + tester.lengthOfLastWord(s));
        }
    }
}

题目本身还是非常简单的, 反正不能简单的就认为直接一个 split 就行了, 因为这里既然题目要求是数最后一个 word, 那么肯定最后会有什么 list 整个很长的 case 来浪费你的时间;

流尾处理

这个也是一个常规问题了, 尤其是段落处理类的算法, 如果不考虑 edge 的话, 很可能最后一个段落结束就会被错过;

最后的速度是6ms (45%), 中规中矩;

这题虽然不用 split, 最后还是有 API 可以做的:

public class Solution {  
    public int lengthOfLastWord(String s) {  
        String trimed = s.trim();  
        return trimed.length() - 1 - trimed.lastIndexOf(" ");  
    }  
}

不过这种基本的算法题目这样做就没有意思了;

这个是 submission 最优解:

public class Solution {  
    public int lengthOfLastWord(String s) {  
        int count = 0;  
        boolean lastspace = false;  
        for (int i = s.length() - 1; i >= 0; i--) {  
            if(!lastspace) {  
                if(s.charAt(i) != ' ') {  
                    lastspace = true;  
                    count++;  
                }                     
            } else {  
                if(s.charAt(i) == ' ')  
                    break;  
                count++;  
            }      
        }          
        return count;  
    }  
}

我一开始的想法也是用 count, 但是感觉一直++可能要占用速度, 不过最后看来, 好像也没有多大的影响. 而且他这个代码的逻辑其实比我的逻辑要简练不少;
count 方式的好处是, 你一个 count 反映的其实是一个过程, 整个过程中所有被你走过的entry, 全都被 count 进去了. 我的思路是使用始末 index, 这个方法的难度在于, 结束的 index 的更新你是要考虑流尾处理的. 但是用 count 就不用考虑;

这个也许可以总结成一个长期的规律; index类的 variable 比 length 类的 var 更容易被流尾问题所影响;

这个是 discussion 上的最优解:

class Solution {  
public:  
    int lengthOfLastWord(string s) {   
        int len = 0, tail = s.length() - 1;  
        while (tail >= 0 && s[tail] == ' ') tail--;  
        while (tail >= 0 && s[tail] != ' ') {  
            len++;  
            tail--;  
        }  
        return len;  
    }  
};

这个的逻辑更加直白, 直接手动把所有末尾的空格全部都跳过, 然后走到看到第一个空格为止;

Problem Description

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.

Difficulty:Easy
Total Accepted:147.8K
Total Submissions:465.4K
Contributor: LeetCode
Related Topics
string