LeetCode字符串专栏（简单：1

LeetCode字符串专栏（简单：1

接着数学专栏刷的同时，同时开辟字符串专栏，这一栏中的简单题有很多都是和别的专栏重合的，所以下面的题目选自不重合的新题。

1. 最长公共前缀（14）
   
     第一种方法是外层遍历数组中每一个字符串，内层遍历每个字符串的每一个字符，与结果字符串初始（第一个字符串）相比较，如果到特定位置不同，则“砍下”不同字符往后的子字串串，依次这么“砍”下去，最后就会得到公共的结果字符串。需要注意的是如果当前字符串比当前结果字符串长度还短，那么理应将结果字符串替换为当前字符串。
   
     这道题的第二种方法是外层遍历第一个字符串的每一个字符，内层遍历整个数组，数组每一个对应位置上的字符与之相比较，如果相同，将该字符连接到结果字符串，如果不同，那么直接返回上一次得到的结果。
   
     第三种方法是二分查找，很显然，这种字符串匹配问题肯定是可以使用二分查找的，尤其在字符串特别长的时候，二分查找是个很好的选择。

2. 有效的括号（20）
   
   
     这道题很重要！试想，如果要编写一个编译器，那么最常见的功能就是括号匹配了吧。
   
     这道题主要使用栈来进行符号匹配操作，具体操作是：从头到尾遍历字符串中每一个符号，遇到左括号就push到栈中，遇到右括号，就将栈顶pop出来，如果栈顶元素不等于对应右括号的左括号，那么就不匹配。设置一个计数器，用来计算push与pop操作，如果到最后push和pop次数相同，那么count就会等于0，此时可以认为是符号匹配的。

3. 实现strStr()（28）
   
     这道题我一看题目，就知道是KMP算法，虽然之前在考研的时候反复练过这个算法，但是还是没记住￣□￣｜｜。这次借着这道题，完完整整的理解这个算法。
     首先是BF法，也即暴力求解，两层循环解决问题。但是对于暴力求解，有一个问题，就是当出现不匹配的时候，它会同时回退主串和字串的指针，时间复杂度为O（M*N）。
   
     具体的KMP解释参考这篇文章，讲的很详细。
   /
     KMP 算法的核心思想：永不回退主串的指针 i，不走回头路，而是借助next数组中储存的信息把字串移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以可以认为它是一种动态规划算法。
     KMP中next数组的计算只和模式串（子串）有关，也就是说对于任何主串，在与子串匹配过程中，只要特定模式串的next求好之后，就可以进行KMP算法了。
     这篇对于KMP的讲解也很详细：.html
     我们需要先计算出next数组，next数组的定义是：取当前字符前的字符串中前缀字串和后缀字串相等的最大字串长度：
   
   

4. 报数（38）
   
     这道题我一开始已经写出来了，但是字符串拼接我用的是concat，不知道为什么不对，最后直接用+，AC！
   
     concat之所以不行如下：他不会改变原始数据，而+可以。
   

5. 最后一个单词的长度（58）
   
     这道题需要注意的是下面这种情况，所以拿到s后需要首先把字符串进行尾部去空，然后再从后到前计算最后一个字符的长度。
   
     另外trim也可以实现相同的操作。
   
   

6. 二进制求和（67）
   
     这个上次写过了，忘记保存了。。直接贴代码吧（原谅我的懒惰~）
   

7. 验证回文串（125）
   
     这道题思想并不难，关键在于对回文串的处理（去掉字母外的其他字符，并转化为小写）