NumberOfSegmentsInAString [source code]

public class NumberOfSegmentsInAString {
static
/******************************************************************************/
public class Solution {
    public int countSegments(String s) {
        char[] chs = s.toCharArray();
        boolean inSegment = false;
        int count = 0;
        for (char c : chs) {
            if (!inSegment && c != ' ') {
                inSegment = true;
            } else if (inSegment && c == ' ') {
                inSegment = false;
                count++;
            }
        }
    if (inSegment) count++;
        return count;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        NumberOfSegmentsInAString.Solution tester = new NumberOfSegmentsInAString.Solution();
        String[] inputs = {
            "Hello, my name is John",
            "",
            ", , , ,        a, eaefa",//6
        };
        for (String s : inputs) System.out.println(s + " -> " + tester.countSegments(s));
    }
}

刚开始的想法是用 regex 的 split 做. 还是有一点儿坑的:

java> "".split(" ")  
java.lang.String[] res0 = [""]  
java> "a b c".split(" ")  
java.lang.String[] res1 = ["a", "b", "c"]

可以看到, ""居然也能被 split 出来一个结果(这个 array 的长度是1); 当然, 这个并不是不合理, 这个 API 好像就是这么设计的, 但是这个并不符合这里的要求;

split最后不行, 第三个 case 被 break 了;

java> ", , , ,        a, eaefa".split(" ")  
java.lang.String[] res0 = [",", ",", ",", ",", "", "", "", "", "", "", "", "a,", "eaefa"]

因为 split 并不会完成一个contiguous空格的合并. 当然你可以后续再加一个 pass 来处理一下这个string array, 不过这个就没有什么必要了; 干脆直接就一开始自己用 stream 算法来做算了;

if (s.equals("")) return 0;

在做 split 的时候,又碰到这个问题, 就是String equality test的时候, 在自己的 JVM 上面,直接用 == 是可以的, 但是跑到 LeetCode 的 OJ 上面, 就不接受了. 所以最好还是用 equals.

判断上下边沿的问题, 很容易的一个坑就是最后的末尾的边界效应怎么处理; 这个好像也是以前被坑过一次了;

最后的速度是2ms (75%), 还可以;

看了一下条形图, 好像是最优解了;

discussion 认为好像这题还是可以用 regex 来做:

public int countSegments(String s) {  
    return ("x " + s).split(" +").length - 1;  
}

不是太懂这个是什么原理, 不过试了一下, 是对的;

discussion 大部分的最优解都是这个思路:

public int countSegments(String s) {  
    int res=0;  
    for(int i=0; i<s.length(); i++)  
        if(s.charAt(i)!=' ' && (i==0 || s.charAt(i-1)==' '))  
            res++;          
    return res;  
}  

Time complexity:  O(n)  
Space complexity: O(1)

他们每一个 iteration 要两个array access. 不过其实估计也差不多, 我虽然只有一个array access, 不过我要 access 一个 boolean, 最后速度估计差别不会太大;

Problem Description

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5
Difficulty:Easy
Category:Algorithms
Acceptance:36.72%
Contributor: love_Fawn
Related Topics
string