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

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. 😉😃💗