字符串总结
2020-05-29 11:29:47
# leetcode
# 总结
# 算法
String总结
String常用api
| 方法 | String |
|---|---|
| 增 | String concat(String str): 将指定字符串连接到此字符串的结尾。（不建议使用） |
| 删 | 字符串不能随便删，trim除外，放到下面部分了。 |
| 改 | char[] toCharArray()： 将此字符串转换为一个新的字符数组。 String substring(int beginIndex)： 返回一个新的字符串，从beginIndex到结尾，它是此字符串的一个子字符串。 String substring(int beginIndex, int endIndex): 返回一个新的字符串，下标从beginIndex到endIndex - 1，是一个左闭右开的区间，它是此字符串的一个子字符串。 String trim(): 返回字符串的副本，忽略前导空白和尾部空白。 String toUpperCase(): 将此 String 中的所有字符都转换为大写。 String toLowerCase(): 将此 String 中的所有字符都转换为小写。 String replace(char oldChar, char newChar)： 返回一个新的字符串，它是通过用 newChar 替换此字符串中出现的所有 oldChar 得到的。 String replaceAll(String regex, String replacement)： 使用给定的 replacement 替换此字符串所有匹配给定的正则表达式的子字符串。 String replaceFirst(String regex, String replacement)：使用给定的 replacement 替换此字符串匹配给定的正则表达式的第一个子字符串。 |
| 查 | int length(): 返回此字符串的长度。int indexOf(int ch) char charAt(int index)**：返回指定索引处的 char 值 **int indexOf(int ch, int fromIndex): 返回在此字符串中第一次出现指定字符处的索引，从指定的索引开始搜索（包含），没有则返回-1。 int indexOf(String str): 返回指定子字符串在此字符串中第一次出现处的索引，没有则-1。 int indexOf(String str, int fromIndex): 返回指定子字符串在此字符串中第一次出现处的索引，从指定的索引开始，没有则-1。 int lastIndexOf(int ch): 返回指定子字符在此字符串中最右边出现处的索引，没有则-1。 int lastIndexOf(int ch, int fromIndex): 返回指定字符在此字符串中最后一次出现处的索引，从指定的索引处开始进行反向搜索，没有则-1。 int lastIndexOf(String str): 返回指定子字符串在此字符串中最右边出现处的索引，没有则-1。 int lastIndexOf(String str, int fromIndex): 返回指定子字符串在此字符串中最后一次出现处的索引，从指定的索引开始反向搜索，没有则-1。 boolean startsWith(String prefix, int toffset): 测试此字符串从指定索引开始的子字符串是否以指定前缀开始，offset是空出字符的数量，也是开始查找的index。 boolean startsWith(String prefix): 测试此字符串是否以指定的前缀开始。 |
String经典算法
KMP算法
KMP算法是用于字符串匹配的经典算法，但是实现起来比较复杂，故不推荐使用而已，它的最坏时间复杂度是O(m + n)，m和n分别是待匹配字符串和目标字符串的长度。
KMP算法解释起来很麻烦，可以结合以下资料来观看（因为懒得画图，这里需要很土图示来解释）：
其实它的核心思想就是对于某次错误的字符串匹配后，不要再进行重新从头匹配，而是跳转到某个合适的位置。例如：
s1: "aaaabababba"
s2: "ababb"
希望在s1中找到s2首次出现的位置
假设我们某次匹配到了s1字符串的子串，aaaabababba，和s2的(ababb)只差了一位，按照传统做法，我们这时候会将s1的指针右移一位，然后重新开始匹配。
但是我们细心一点可以发现，s1红色的那个子串，最后不匹配的a的前面有ab，而ab又恰好是s2的开头两个字符，也就是说我们可以从s2的第三位开始比较起来，也就是说我们下一个希望比较的s1的子字符串是aaaabababba，我们可以发现刚好符合条件；如果使用老的方法则是将s1的pointer右移一位，比较babab和s2，KMP算法可以直接跨越这一步。这就是KMP算法的核心思想。
KMP算法实现：
LeetCode 28. Implement strStr()1 |