算法（4）：字符串

最近两天有点高产（只是说高数量，不是指高质量......），希望可以坚持下去，至少把这个算法系列先写完，给自己来点成就感......

目录：
算法：附录
 算法（1）：递归
 算法（2）：链表
 算法（3）：数组
 算法（4）：字符串
 算法（5）：二叉树
 算法（6）：二叉查找树
 算法（7）：队列和堆栈（附赠BFS和DFS）
算法（8）：动态规划
 算法（9）：哈希表
 算法（10）：排序
 算法（11）：回溯法
 算法（12）：位操作

字符串（String）

字符串可以简单理解为一个存放 unicode 编码的字符数组。大家可以对字符串执行几乎所有数组可以执行的操作。但是两者之间肯定是有一些不同之处的，甚至在不同语言当中，字符串的特性也会有所区别（如让人迷惑的 ‘==’ 操作）。当然，本算法系列主要针对python语言做讲解~
不过，还是会简单说一下不同语言下string的区别~

比较操作：
我们如果要使用 ‘==’ 来进行两个字符串的比较，那么要看一看这门语言是否支持操作符重载（operator overloading），如果支持，如C++，那么我们可以比较两个字符串是否内容一致。如果不支持，如Java，那么当我们使用‘==’时，相当于是在判断两个string是否为同一个对象。
python，此时联手C++，也是可以用等号来判断两个string是否内容相同~
可变和不可变（也就是能不能修改）：
在C++里面，字符串是可变的，相当于你操作字符串，可以像操作数组一样，使用索引更改元素。但是在 Java 里，字符串则不可变，如执行s = 'good evening'; s[4] = ','等类似修改字符串内容的操作，是不可以的。如果你想要哪怕只是更改一个字符，也需要新建一个字符串对象。
而python，本次站队Java，将字符串视为不可变对象。
当字符串不可变时，比如执行一个 s += 'a'操作，时间复杂度为 $O(n)$ （其中n为字符串s的长度）。因为这个时候，是建立了一个新字符串，分配给它（n+1)的空间，然后将字符串s和字符 ‘a' 复制过去。
所以，如果你真的想要一个可修改的字符串，那么可以尝试建立一个字符数组（char array）。如果你很频繁的给字符串添加内容，则不妨使用其他数据结构，如Java里的（StringBuilder）。

问题1：求几个字符串的最长公共前缀（ longest common prefix）
例子：
输入: ["flower","flow","flight"]
输出: "fl"

def longestCommonPrefix( strs: list) -> str:
    if not strs:
        return ""

    for i, letter_group in enumerate(zip(*strs)):
        if len(set(letter_group)) > 1:
            return strs[0][:i]
    else:
        return min(strs)

if __name__ == '__main__':
    s = ["flower","flow","flight"]
    ans = longestCommonPrefix(s)
    print(ans)

问题2：翻转字符串中的单词（Reverse Words in a String），字符串是一个句子，由若干单词组成，每个单词之间由空格隔开，现在要将字符串中单词翻转，例子如下。
输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc"
用python内置函数很容易就写出来。

def reverseString( s: str) -> str:
    a = s.split()
    for i, j in enumerate(a):
        a[i] = a[i][::-1]
    return ' '.join(a)

if __name__ == '__main__':
    s = "Let's take LeetCode contest"
    ans = reverseString(s)
    print(ans)

问题3：

没找到啥有趣的好题，例题先放放，我看到了有趣的会立刻补上来。

问题4：

问题5：

最后编辑于：2019.06.10 15:41:55