剑指Offer 05: 替换空格
题目描述
请实现一个函数，把字符串
s中的每个空格替换成"%20"
建立模型
- 这就是一个遍历字符串元素替换的问题
需要注意的就是Python/Java中的str是不可变类型，需要转化成可变类型的List/StringBuilder拼接
代码实现
# Python3 实现
def replaceSpace(self, s: str) -> str:
res = []
for ch in s:
if ch == ' ':
res.append('%20')
else:
res.append(ch)
return ''.join(res)
// Java 实现
public String replaceSpace(String s) {
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == " ") {
sb.append("%20");
}
else {
sb.append(c);
}
}
return sb.toString();
}
LeeCode 28: 实现strStr()
题目描述
给你两个字符串
haystack和needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1
建立模型
暴力匹配
- 让字符串 needle 与 haystack 所有长度相等的子串匹配一次
时间复杂度 O(M * N)，M为needle字符串长度，N为haystack字符串长度
KMP算法
来自我的另一篇文章KMP字符串匹配
代码实现
# Python3 暴力匹配
def strStr(self, haystack: str, needle: str) -> int:
if needle is None or needle == ' ':
return 0
i, j = 0, len(needle)
while j <= len(haystack):
if haystack[i:j] == needle:
return i
i += 1
j += 1
return -1
// Java 暴力匹配
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0) {
return 0;
}
int i = 0, j = needle.length();
while (j <= haystack.length()) {
if (haystack.substring(i, j).equals(needle)) {
return i;
}
i += 1;
j += 1;
}
return -1;
}
LeeCode 459: 重复的子字符串
题目描述
给定一个非空的字符串
s，检查是否可以通过由它的一个子串重复多次构成。
建立模型
暴力求解
枚举子串的长度 {1 ~ \(\frac{len(s)}{2}\)}，最少需要重复两次
如果字符串s满足由一个子串重复多次构成，假设子串长度为m，则有如下关系：
\[s[i] == s[i - m] \quad \forall i \ge m
\]
巧妙解法
- 如果字符s满足由一个子串重复多次构成，则 \(s = n * s_1\)
将字符串拷贝一份得到\(s^{'} = 2*s = 2*n*s_1\)
破坏首尾两个\(s_1\)，中间还存在 \(2*n - 2 \ge n (n \ge 2)\)
所以原字符串s应该是\(s^{'}\)的子串
代码实现
# Python3 暴力求解
def repeatedSubstringPattern(self, s: str) -> bool:
# 枚举子串长度
for i in range(1, len(s) // 2 + 1):
if len(s) % i == 0:
flag = True
for j in range(i, len(s)):
if s[j] != s[j - i]:
flag = False
break
if flag:
return True
return False
# Python3 巧妙求解
def repeatedSubstringPattern(self, s: str) -> bool:
# 分别去除首尾单个字符破坏子串
return s in (s + s)[1:-1]
// Java 暴力求解
boolean repeatedSubstringPattern(String str) {
for (int i = 1; i < str.length() / 2 + 1; i++) {
if (str.length() % i == 0) {
boolean flag = true;
for (int j = i; j < str.length(); j++) {
if (str.charAt(j) != s.charAt(j - i)) {
flag = false;
break;
}
}
if (flag) {
return true;
}
}
}
return false;
}
// Java 巧妙解法
boolean repeatedSubstringPattern(String str) {
String s = str.concat(str).substring(1, 2*str.length() - 1);
if (s.index(str) != -1) {
return true;
}
return false;
}
