本文共 2389 字,大约阅读时间需要 7 分钟。
字符串基础问题
https://leetcode-cn.com/problems/to-lower-case/ √ https://leetcode-cn.com/problems/length-of-last-word/ √ https://leetcode-cn.com/problems/jewels-and-stones/ √ https://leetcode-cn.com/problems/first-unique-character-in-a-string/ √ https://leetcode-cn.com/problems/string-to-integer-atoi/ √ 字符串操作问题 https://leetcode-cn.com/problems/longest-common-prefix/description/ √ https://leetcode-cn.com/problems/reverse-string √ https://leetcode-cn.com/problems/reverse-string-ii/ √ https://leetcode-cn.com/problems/reverse-words-in-a-string/ √ https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/ √ https://leetcode-cn.com/problems/reverse-only-letters/ √ 异位词问题 https://leetcode-cn.com/problems/valid-anagram/ √ https://leetcode-cn.com/problems/group-anagrams/ √ https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/ √ 回文串问题 https://leetcode-cn.com/problems/valid-palindrome/ √ https://leetcode-cn.com/problems/valid-palindrome-ii/ √ https://leetcode-cn.com/problems/longest-palindromic-substring/ 最长子串、子序列问题 https://leetcode-cn.com/problems/longest-common-subsequence/ https://leetcode-cn.com/problems/edit-distance/ https://leetcode-cn.com/problems/longest-palindromic-substring/python 和 Java字符串是不可变的,c/C++字符串是可变的
第一,实际的软件开发中,大部分情况下,模式串和主串的长度都不会太长。而且每次模式串与主串中的子串匹配的时候,当中途遇到不能匹配的字符的时候,就可以就停止了,不需要把 m 个字符都比对一下。所以,尽管理论上的最坏情况时间复杂度是 O(n*m),但是,统计意义上,大部分情况下,算法执行效率要比这个高很多。第二,朴素字符串匹配算法思想简单,代码实现也非常简单。简单意味着不容易出错,如果有 bug 也容易暴露和修复。在工程中,在满足性能要求的前提下,简单是首选。这也是我们常说的KISS(Keep it Simple and Stupid)设计原则。
RK 算法整体的时间复杂度就是 O(n)。
转载地址:http://exjwi.baihongyu.com/