LeetCode刷题记录（字符串篇）
LeetCode刷题记录（字符串篇），个人向。
为了锻炼代码能力，会交替使用不同编程语言完成答案。
[344] Reverse String
难度：Easy
语言：C++
题目描述。
左右指针往中间靠拢即可，无难度。
void reverseString(vector<char>& s) {
char tmp;
for (int left = 0, right = s.size() - 1; left < right; left++, right--) {
tmp = s[left];
s[left] = s[right];
s[right] = tmp;
}
}
[541] Reverse String II
难度：Easy
语言：Python
题目描述。
按照题目要求反转字符串即可，基本无难度。
def reverseStr(self, s: str, k: int) -> str:
s = list(s)
cur = 0
size = len(s)
while cur < size:
left = cur
right = min(left + k - 1, size - 1)
while left < right:
tmp = s[left]
s[left] = s[right]
s[right] = tmp
left += 1
right -= 1
cur += 2 * k
return "".join(s)
[151] Reverse Words in a String
难度：Medium
语言：Rust
题目描述。
最简单的方法是先分好词，然后翻转然后拼起来即可。但为了增加挑战性，我们希望能只用O(1)的额外空间，即in-place地解决问题。
那么如何in-place修改呢？我们可以考虑翻转两次。第一次翻转整个字符串，第二次再翻转各个单词，如此单词内部顺序正确，整体的单词顺序也被翻转过来了。除此之外，我们还需要先去除多余空格。由此，可得到以下步骤：
- 去除多余空格。
- 翻转字符串，然后翻转单词。
对于去除空格，我们使用了快慢指针的方式，即一个快指针在前面扫描，遇到多余的空格就不处理，否则把字符填到慢指针的地方，最后resize一下。
最后得到的代码如下。
impl Solution {
pub fn reverse(s: &mut Vec<char>, mut begin: usize, mut end: usize) {
while begin < end {
let temp = s[begin];
s[begin] = s[end];
s[end] = temp;
begin += 1;
end -= 1;
}
}
pub fn remove_extra_spaces(s: &mut Vec<char>) {
let mut slow: usize = 0;
let len = s.len();
let mut i: usize = 0;
while i < len {
if !s[i].is_ascii_whitespace() {
if slow != 0 {
s[slow] = ' ';
slow += 1;
}
while i < len && !s[i].is_ascii_whitespace() {
s[slow] = s[i];
slow += 1;
i += 1;
}
}
i += 1;
}
s.resize(slow, ' ');
}
pub fn reverse_words(s: String) -> String {
let mut s = s.chars().collect::<Vec<char>>();
Self::remove_extra_spaces(&mut s);
let len = s.len();
Self::reverse(&mut s, 0, len - 1);
let mut start = 0;
for i in 0..=len {
if i == len || s[i].is_ascii_whitespace() {
Self::reverse(&mut s, start, i - 1);
start = i + 1;
}
}
s.iter().collect::<String>()
}
}
[28] Find the Index of the First Occurrence in a String
难度：Easy
语言：Python
题目描述。
使用了KMP算法。关于KMP算法，具体可以看这篇文章。
简单来说，先构造next表，该表记录了needle从开始到index所处位置的最长公共前后缀的长度。之后在查找时，若needle和haystack当前位置匹配失败，则可根据next表找到needle中和后缀相同的前缀所处的末尾位置，然后再从该位置继续匹配，这样可省去前缀的重复匹配的开销。该算法的时间复杂度为O(m+n)。
class Solution:
def getNext(self, needle: str) -> List:
j = 0
i = 1
length = len(needle)
next_table = [0] * length
while i < length:
while j > 0 and needle[i] != needle[j]:
j = next_table[j - 1]
if needle[i] == needle[j]:
j += 1
next_table[i] = j
i += 1
return next_table
def strStr(self, haystack: str, needle: str) -> int:
next_table = self.getNext(needle)
j = 0
i = 0
haystack_length = len(haystack)
needle_length = len(needle)
while i < haystack_length:
while j > 0 and haystack[i] != needle[j]:
j = next_table[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == needle_length:
return i - needle_length + 1
i += 1
return -1
[459] Repeated Substring Pattern
难度：Easy
语言：C++
题目描述。
看见题目后先自己写了个简单解法。Naive的想法就是把pattern重复几次到s的长度，然后再看两者是否相等即可。其中又有一些小优化，例如pattern的长度最长只需要到total_length的一半，以及total_length % i == 0才需要继续判断。
这种方法是可以通过测试的， 但还有更高效的算法。可以使用KMP算法来解决该问题。
在[28] Find the Index of the First Occurrence in a String中，我们提到了通过构建next表来存储最长公共前后缀的长度，在该题中也一样，先对字符串s构建next表。如果s存在最小重复子串单位，则total_length - common_length就是该最小单位的长度。最后，我们再检查是否total_length % diff == 0即可判断该字符串s是否由重复的子字符串构成。
更详细的解释可参考这篇文章。
class Solution {
public:
void getNext(int* next, string s) {
int j = 0;
int length = s.size();
next[0] = j;
for (int i = 1; i < length; ++i) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
++j;
}
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
int total_length = s.size();
vector<int> next(total_length);
getNext(&next[0], s);
int common_length = next[total_length - 1];
if (common_length == 0) {
return false;
}
int diff = total_length - common_length;
if (total_length % diff == 0) {
return true;
} else {
return false;
}
}
bool repeatedSubstringPatternNaive(string s) {
string pattern(1, s[0]);
int total_length = s.size();
int i = 1;
while (i <= total_length / 2) {
if (total_length % i == 0) {
int times = total_length / i;
string result = pattern;
while (times-- > 1) {
result += pattern;
}
if (result == s) {
return true;
}
}
pattern += s[i];
++i;
}
return false;
}
};
总结
其实本质算法上看，字符串与数组并无区别，只是元素变成了字符而已。
- 字符串的一些题涉及到了双指针的方法。其中，双指针又可用于反转字符串。[151] Reverse Words in a String又在此基础上更进一步，需要把字符串翻转两次，其中第一次翻转整个字符串，第二次仅翻转单词来达到仅翻转所有单词顺序的效果。
- 另一部分题用到了KMP算法。KMP算法通过记录了从开始到字符串各个位置子串的最长公共前后缀的长度。通过该记录，可以在查找子串的过程中失败时方便回退到前缀末尾对应的位置，跳过已匹配的部分，降低时间复杂度。[459] Repeated Substring Pattern还通过数学原理判断了是否存在可重复的子串来构成原字符串。具体来说，通过
total_length和common_length的差找到了可能的最小重复单位的长度，再通过取模判断原字符串是否是最小单位的倍数。