[Leetcode][1816. 截断句子] 3种方法:正则表达式,模拟和优化
By Long Luo
Leetcode 1816. 截断句子 题解。
方法一:Regex
很简单,首先想到的是正则表达式,根据空格分割单词。1
2
3
4
5
6
7
8
9
10public 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
16public 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 | public boolean buddyStrings(String s, String goal) { |
复杂度分析
时间复杂度:\(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. 😉😃💗