58 Length of Last Word

title: Length of Last Word
tags:
- length-of-last-word
- No.58
- simple
- finite-automata
- string

Problem

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.

Example:

Input: "Hello World"
Output: 5

Corner Cases

begin with " "
end with " "
empty string ""
single word "a"

Solutions

Finite Automata

Use finite automata to solve this problem. The transition table is:

state	`" "`	`"\w"`
0	1(`l=0`)	2(`l++`)
1	1(`l=0`)	2(`l++`)
2	1(`l=0`)	2(`l++`)

But this table cannot deal with strings ending with " ", thus we should adjust the ending index, like String.rstrip() in python and String.trim() in java.

The running time is $O(n)$ .

class Solution {
    public int lengthOfLastWord(String s) {
        if (s.equals("")) {return 0;}

        int[][] dfa = new int[3][2];
        for (int i=0; i<3; i++) {
            dfa[i][0] = 1;
            dfa[i][1] = 2;
        }

        String[] t = s.split("");
        int      e = t.length - 1;
        while (t[e].equals(" ")) {
            e--;
            if (e < 0) {break;}
        }

        int l = 0;
        int j = 0;
        for (int i=0; i<=e; i++) {
            j = dfa[j][f(t[i])];
            l = (j == 2) ? l + 1 : 0;
        }
        return l;
    }

    private int f(String x) {
        return (x.equals(" ") ? 0 : 1);
    }
}