[Leetcode][1816. 截断句子] 3种方法：正则表达式，模拟和优化

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2k 阅读时长 ≈ 2 分钟

By Long Luo

Leetcode 1816. 截断句子 题解。

方法一：Regex

很简单，首先想到的是正则表达式，根据空格分割单词。

1
2
3
4
5
6
7
8
9
10
public String truncateSentence(String s, int k) {
	String[] words = s.split("\\s+");
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < k; i++) {
		sb.append(words[i]).append(" ");
	}

	sb.deleteCharAt(sb.length() - 1);
	return sb.toString();
}

复杂度分析

  • 时间复杂度：\(O(N)\)，其中\(N\)为\(\textit{s}\)的长度。

  • 空间复杂度：\(O(N)\)。

方法二：模拟

简单的模拟，统计空格与句子结尾的数目来统计单词数，当已经有\(k\)个单词时，返回答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String truncateSentence(String s, int k) {
	StringBuilder sb = new StringBuilder();
	int len = s.length();
	for (int i = 0; i < len; i++) {
		sb.append(s.charAt(i));
		if (s.charAt(i) == ' ') {
			k--;
		}
		if (k == 0) {
			sb.deleteCharAt(sb.length() - 1);
			break;
		}
	}

	return sb.toString();
}

复杂度分析

  • 时间复杂度：\(O(N)\)，其中\(N\)为\(\textit{s}\)的长度。

  • 空间复杂度：\(O(N)\)。

方法三：优化

我们可以只记录最后截断的下标\(\textit{end}\)，返回句子\(\textit{s}\)在\(\textit{end}\)处截断的句子。

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
public boolean buddyStrings(String s, String goal) {
    if (s == null || goal == null || s.length() <= 1 || goal.length() <= 1
            || s.length() != goal.length()) {
        return false;
    }

    int len = s.length();
    int first = -1;
    int second = -1;
    if (s.equals(goal)) {
        int[] count = new int[26];
        for (int i = 0; i < len; i++) {
            count[s.charAt(i) - 'a']++;
            if (count[s.charAt(i) - 'a'] > 1) {
                return true;
            }
        }
        return false;
    } else {
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) != goal.charAt(i)) {
                if (first == -1) {
                    first = i;
                } else if (second == -1) {
                    second = i;
                } else {
                    return false;
                }
            }
        }
    }

    if (first != second && first >= 0 && second >= 0 && s.charAt(first) == goal.charAt(second) && s.charAt(second) == goal.charAt(first)) {
        return true;
    }

    return false;
}

复杂度分析

  • 时间复杂度：\(O(N)\)，其中\(N\)为\(\textit{s}\)的长度。

  • 空间复杂度：\(O(1)\)。

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗