HiSEN

计算长度最大的子串长度(按空格分割) - 多种方式

发表于 | 分类于

一、背景

今天中午一个朋友问我一个问题没来得及回，现在折腾一下;
问题：有一个包含以N个空格分割的字符串，求最大子串的长度，要求时间空间复杂度最优;

二、方案：

  1. 朋友给人方案：直接split分割遍历数组，找出最大值;
  2. 面试官的方案：使用StringTokenizer，找出最大值;
  3. 我想到的方案：indexOf计算index差值，找出最大值;

三、结果：

封装的代码比较复杂，目前来看不在么好分析时间复杂度和空间复杂度；
于是就直观得对比了一下时间；

1
2
3
4
//        output
//        use(nano): 15486049, by 方案3
//        use(nano): 66060102, by 方案2
//        use(nano): 80844275, by 方案1

有时间再深入了解下StringTokenizer的源码

四、代码对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
String oriStr = "aa aa aaaa aaa a a a aa aa a";
int times = 100000;
// 自定义实现
final long start1 = System.nanoTime();
for (int i = 0; i < times; i++) {
    String splitStr = " ";
    findMaxLength(oriStr, splitStr);
}
final long end1 = System.nanoTime();

// 利用 StringTokenizer
final long start2 = System.nanoTime();
for (int i = 0; i < times; i++) {
    findMaxLength4StringTokenizer(oriStr);
}
final long end2 = System.nanoTime();

// 利用 Split
final long start3 = System.nanoTime();
for (int i = 0; i < times; i++) {
    String splitStr = " ";
    findMaxLength4Split(oriStr, splitStr);
}
final long end3 = System.nanoTime();

System.out.println("use(nano): " + (end1 - start1) + ", by findMaxLength");
System.out.println("use(nano): " + (end2 - start2) + ", by findMaxLength4StringTokenizer");
System.out.println("use(nano): " + (end3 - start3) + ", by findMaxLength4Split");
//        output
//        use(nano): 15486049, by findMaxLength
//        use(nano): 66060102, by findMaxLength4StringTokenizer
//        use(nano): 80844275, by findMaxLength4Split

五、完整代码

github也有：https://github.com/hisenyuan/IDEAPractice/blob/master/src/main/java/com/hisen/interview/TestStringTokenizer.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * @Author hisenyuan
 * @Description 计算长度最大的子串长度(按空格分割), 自定义实现比较优
 * @Date 2019/3/26 20:53
 */
public class TestStringTokenizer {
    public static void main(String[] args) {
        String oriStr = "aa aa aaaa aaa a a a aa aa a";
        int times = 100000;
        // 自定义实现
        final long start1 = System.nanoTime();
        for (int i = 0; i < times; i++) {
            String splitStr = " ";
            findMaxLength(oriStr, splitStr);
        }
        final long end1 = System.nanoTime();

        // 利用 StringTokenizer
        final long start2 = System.nanoTime();
        for (int i = 0; i < times; i++) {
            findMaxLength4StringTokenizer(oriStr);
        }
        final long end2 = System.nanoTime();

        // 利用 Split
        final long start3 = System.nanoTime();
        for (int i = 0; i < times; i++) {
            String splitStr = " ";
            findMaxLength4Split(oriStr, splitStr);
        }
        final long end3 = System.nanoTime();

        System.out.println("use(nano): " + (end1 - start1) + ", by findMaxLength");
        System.out.println("use(nano): " + (end2 - start2) + ", by findMaxLength4StringTokenizer");
        System.out.println("use(nano): " + (end3 - start3) + ", by findMaxLength4Split");
//        output
//        use(nano): 15486049, by findMaxLength
//        use(nano): 66060102, by findMaxLength4StringTokenizer
//        use(nano): 80844275, by findMaxLength4Split
    }

    private static void findMaxLength4StringTokenizer(String oriStr) {
        int maxLength = 0;
        final StringTokenizer stringTokenizer = new StringTokenizer(oriStr);
        while (stringTokenizer.hasMoreElements()) {
            final int length = stringTokenizer.nextToken().length();
            maxLength = length > maxLength ? length : maxLength;
        }
//        System.out.println("max: " + maxLength);
    }

    private static void findMaxLength(String oriStr, String splitStr) {
        int index = 0;
        final int maxIndex = oriStr.lastIndexOf(splitStr);
        int maxLength = oriStr.length() - maxIndex;
        while (index < maxIndex) {
            final int currentIndex = oriStr.indexOf(splitStr, index);
            int currLength = currentIndex - index;
            maxLength = currLength > maxLength ? currLength : maxLength;
            index = currentIndex + splitStr.length();
        }
//        System.out.println("max: " + maxLength);
    }

    private static void findMaxLength4Split(String oriStr, String splitStr) {
        int maxLength = 0;
        final String[] strings = oriStr.split(splitStr);
        for (String str : strings) {
            final int length = str.length();
            maxLength = length > maxLength ? length : maxLength;
        }
//        System.out.println("max: " + maxLength);
    }
}