经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 其他 » 职业生涯 » 查看文章
[算法总结] 13 道题搞定 BAT 面试——字符串
来源：cnblogs　　作者：尾尾部落　　时间：2018/9/25 19:24:34　　对本文有异议

本文首发于我的个人博客：尾尾部落

1. KMP 算法

谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。

具体算法细节请参考：

1.1 BM 算法

BM算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。
字符串匹配的KMP算法

2. 替换空格

剑指offer：替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

  1. public class Solution {
  2.     public String replaceSpace(StringBuffer str) {
  3.         StringBuffer res = new StringBuffer();
  4.         int len = str.length() - 1;
  5.         for(int i = len; i >= 0; i--){
  6.             if(str.charAt(i) == ' ')
  7.                 res.append("02%");
  8.             else
  9.                 res.append(str.charAt(i));
  10.         }
  11.         return res.reverse().toString();
  12.     }
  13. }

3. 最长公共前缀

Leetcode: 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。


首先对字符串数组进行排序，然后拿数组中的第一个和最后一个字符串进行比较，从第 0 位开始，如果相同，把它加入 res 中，不同则退出。最后返回 res

  1. class Solution {
  2.     public String longestCommonPrefix(String[] strs) {
  3.         if(strs == null || strs.length == 0)
  4.             return "";
  5.         Arrays.sort(strs);
  6.         char [] first = strs[0].toCharArray();
  7.         char [] last = strs[strs.length - 1].toCharArray();
  8.         StringBuffer res = new StringBuffer();
  9.         int len = first.length < last.length ? first.length : last.length;
  10.         int i = 0;
  11.         while(i < len){
  12.             if(first[i] == last[i]){
  13.                 res.append(first[i]);
  14.                 i++;
  15.             }
  16.             else
  17.                 break;
  18.         }
  19.         return res.toString();
  20.     }
  21. }

4. 最长回文串

LeetCode: 最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。


统计字母出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。

  1. class Solution {
  2.     public int longestPalindrome(String s) {
  3.         HashSet<Character> hs = new HashSet<>();
  4.         int len = s.length();
  5.         int count = 0;
  6.         if(len == 0)
  7.             return 0;
  8.         for(int i = 0; i<len; i++){
  9.             if(hs.contains(s.charAt(i))){
  10.                 hs.remove(s.charAt(i));
  11.                 count++;
  12.             }else{
  13.                 hs.add(s.charAt(i));
  14.             }
  15.         }
  16.         return hs.isEmpty() ? count * 2 : count * 2 + 1;
  17.     }
  18. }

4.1 验证回文串

Leetcode: 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。

两个指针比较头尾。要注意只考虑字母和数字字符，可以忽略字母的大小写。

  1. class Solution {
  2.     public boolean isPalindrome(String s) {
  3.         if(s.length() == 0)
  4.              return true;
  5.         int l = 0, r = s.length() - 1;
  6.         while(l < r){
  7.             if(!Character.isLetterOrDigit(s.charAt(l))){
  8.                 l++;
  9.             }else if(!Character.isLetterOrDigit(s.charAt(r))){
  10.                 r--;
  11.             }else{
  12.                 if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
  13.                     return false;
  14.                 l++;
  15.                 r--;
  16.             } 
  17.         }
  18.         return true;
  19.     }
  20. }

4.2 最长回文子串

LeetCode: 最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。


以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。

  1. class Solution {
  2.     private int index, len;
  3.     public String longestPalindrome(String s) {
  4.         if(s.length() < 2)
  5.             return s;
  6.         for(int i = 0; i < s.length()-1; i++){
  7.             PalindromeHelper(s, i, i);
  8.             PalindromeHelper(s, i, i+1);
  9.         }
  10.         return s.substring(index, index+len);
  11.     }
  12.     public void PalindromeHelper(String s, int l, int r){
  13.         while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
  14.             l--;
  15.             r++;
  16.         }
  17.         if(len < r - l - 1){
  18.             index = l + 1;
  19.             len = r - l - 1;
  20.         }
  21.     }
  22. }

4.3 最长回文子序列

LeetCode: 最长回文子序列
给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。
最长回文子序列和上一题最长回文子串的区别是，子串是字符串中连续的一个序列，而子序列是字符串中保持相对位置的字符序列，例如，"bbbb"可以使字符串"bbbab"的子序列但不是子串。


动态规划：
dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])

  1. class Solution {
  2.     public int longestPalindromeSubseq(String s) {
  3.         int len = s.length();
  4.         int [][] dp = new int[len][len];
  5.         for(int i = len - 1; i>=0; i--){
  6.             dp[i][i] = 1;
  7.             for(int j = i+1; j < len; j++){
  8.                 if(s.charAt(i) == s.charAt(j))
  9.                     dp[i][j] = dp[i+1][j-1] + 2;
  10.                 else
  11.                     dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
  12.             }
  13.         }
  14.         return dp[0][len-1];
  15.     }
  16. }

5. 字符串的排列

Leetcode: 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。


我们不用真的去算出s1的全排列，只要统计字符出现的次数即可。可以使用一个哈希表配上双指针来做。

  1. class Solution {
  2.     public boolean checkInclusion(String s1, String s2) {
  3.         int l1 = s1.length();
  4.         int l2 = s2.length();
  5.         int [] count = new int [128];
  6.         if(l1 > l2)
  7.             return false;
  8.         for(int i = 0; i<l1; i++){
  9.             count[s1.charAt(i) - 'a']++;
  10.             count[s2.charAt(i) - 'a']--;
  11.         }
  12.         if(allZero(count))
  13.             return true;
  14.         for(int i = l1; i<l2; i++){
  15.             count[s2.charAt(i) - 'a']--;
  16.             count[s2.charAt(i-l1) - 'a']++;
  17.             if(allZero(count))
  18.                 return true;
  19.         }
  20.         return false;
  21.     }
  22.     public boolean allZero(int [] count){
  23.         int l = count.length;
  24.         for(int i = 0; i < l; i++){
  25.             if(count[i] != 0)
  26.                 return false;
  27.         }
  28.         return true;
  29.     }
  30. }

6. 打印字符串的全排列

剑指offer：字符串的排列
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

把问题拆解成简单的步骤：
第一步求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）；
第二步固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。这样，我们就可以用递归的方法来解决。

  1. public class Solution {
  2.     ArrayList<String> res = new ArrayList<String>();
  3.     public ArrayList<String> Permutation(String str) {
  4.         if(str == null)
  5.             return res;
  6.         PermutationHelper(str.toCharArray(), 0);
  7.         Collections.sort(res);
  8.         return res;
  9.     }
  10.     public void PermutationHelper(char[] str, int i){
  11.         if(i == str.length - 1){
  12.             res.add(String.valueOf(str));
  13.         }else{
  14.             for(int j = i; j < str.length; j++){
  15.                 if(j!=i && str[i] == str[j])
  16.                     continue;
  17.                 swap(str, i, j);
  18.                 PermutationHelper(str, i+1);
  19.                 swap(str, i, j);
  20.             }
  21.         }
  22.     }
  23.     public void swap(char[] str, int i, int j) {
  24.         char temp = str[i];
  25.         str[i] = str[j];
  26.         str[j] = temp;
  27.     }
  28. }

7. 第一个只出现一次的字符

剑指offer: 第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1.

先在hash表中统计各字母出现次数，第二次扫描直接访问hash表获得次数。也可以用数组代替hash表。

  1. import java.util.HashMap;
  2. public class Solution {
  3.     public int FirstNotRepeatingChar(String str) {
  4.         int len = str.length();
  5.         if(len == 0)
  6.             return -1;
  7.         HashMap<Character, Integer> map = new HashMap<>();
  8.         for(int i = 0; i < len; i++){
  9.             if(map.containsKey(str.charAt(i))){
  10.                 int value = map.get(str.charAt(i));
  11.                 map.put(str.charAt(i), value+1);
  12.             }else{
  13.                 map.put(str.charAt(i), 1);
  14.             }
  15.         }
  16.         for(int i = 0; i < len; i++){
  17.             if(map.get(str.charAt(i)) == 1)
  18.                 return i;
  19.         }
  20.         return -1;
  21.     }
  22. }

8. 翻转单词顺序列

剑指offer: 翻转单词顺序列
LeetCode: 翻转字符串里的单词

借助trim()和 split()就很容易搞定

  1. public class Solution {
  2.     public String reverseWords(String s) {
  3.         if(s.trim().length() == 0)
  4.             return s.trim();
  5.         String [] temp = s.trim().split(" +");
  6.         String res = "";
  7.         for(int i = temp.length - 1; i > 0; i--){
  8.             res += temp[i] + " ";
  9.         }
  10.         return res + temp[0];
  12.     }
  13. }

9. 旋转字符串

Leetcode: 旋转字符串
给定两个字符串, A 和 B。
A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。


一行代码搞定

  1. class Solution {
  2.     public boolean rotateString(String A, String B) {
  3.         return A.length() == B.length() && (A+A).contains(B);
  4.     }
  5. }

9.1 左旋转字符串

剑指offer: 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

在第 n 个字符后面将切一刀，将字符串分为两部分，再重新并接起来即可。注意字符串长度为 0 的情况。

  1. public class Solution {
  2.     public String LeftRotateString(String str,int n) {
  3.         int len = str.length();
  4.         if(len == 0)
  5.             return "";
  6.         n = n % len;
  7.         String s1 = str.substring(n, len);
  8.         String s2 = str.substring(0, n);
  9.         return s1+s2;
  10.     }
  11. }

9.2 反转字符串

LeetCode: 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。

  1. class Solution {
  2.     public String reverseString(String s) {
  3.         if(s.length() < 2)
  4.             return s;
  5.         int l = 0, r = s.length() - 1;
  6.         char [] strs = s.toCharArray(); 
  7.         while(l < r){
  8.             char temp = strs[l];
  9.             strs[l] = strs[r];
  10.             strs[r] = temp;
  11.             l++;
  12.             r--;
  13.         }
  14.         return new String(strs);
  15.     }
  16. }

10. 把字符串转换成整数

剑指offer: 把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

  1. public class Solution {
  2.     public int StrToInt(String str) {
  3.         if(str.length() == 0)
  4.             return 0;
  5.         int flag = 0;
  6.         if(str.charAt(0) == '+')
  7.             flag = 1;
  8.         else if(str.charAt(0) == '-')
  9.             flag = 2;
  10.         int start = flag > 0 ? 1 : 0;
  11.         long res = 0;
  12.         while(start < str.length()){
  13.             if(str.charAt(start) > '9' || str.charAt(start) < '0')
  14.                 return 0;
  15.             res = res * 10 + (str.charAt(start) - '0');
  16.             start ++;
  17.         }
  18.         return flag == 2 ? -(int)res : (int)res;
  19.     }
  20. }

11. 正则表达式匹配

剑指offer：正则表达式匹配
请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配


动态规划：
这里我们采用dp[i+1][j+1]代表s[0..i]匹配p[0..j]的结果，结果自然是采用布尔值True/False来表示。
首先，对边界进行赋值，显然dp[0][0] = true，两个空字符串的匹配结果自然为True;
接着，我们对dp[0][j+1]进行赋值，因为 i=0 是空串，如果一个空串和一个匹配串想要匹配成功，那么只有可能是p.charAt(j) == '*' && dp[0][j-1]
之后，就可以愉快地使用动态规划递推方程了。

  1. public boolean isMatch(String s, String p) {
  2.     if (s == null || p == null) {
  3.         return false;
  4.     }
  5.     boolean[][] dp = new boolean[s.length()+1][p.length()+1];
  6.     dp[0][0] = true;
  7.     for (int j = 0; i < p.length(); j++) {
  8.         if (p.charAt(j) == '*' && dp[0][j-1]) {
  9.             dp[0][j+1] = true;
  10.         }
  11.     }
  12.     for (int i = 0 ; i < s.length(); i++) {
  13.         for (int j = 0; j < p.length(); j++) {
  14.             if (p.charAt(j) == '.') {
  15.                 dp[i+1][j+1] = dp[i][j];
  16.             }
  17.             if (p.charAt(j) == s.charAt(i)) {
  18.                 dp[i+1][j+1] = dp[i][j];
  19.             }
  20.             if (p.charAt(j) == '*') {
  21.                 if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
  22.                     dp[i+1][j+1] = dp[i+1][j-1];
  23.                 } else {
  24.                     dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
  25.                 }
  26.             }
  27.         }
  28.     }
  29.     return dp[s.length()][p.length()];
  30. }

12. 表示数值的字符串

剑指offer: 表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示数值。 但是”12e”,”1a3.14″,”1.2.3″,”+-5″和”12e+4.3″都不是。

设置三个标志符分别记录“+/-”、“e/E”和“.”是否出现过。

  1. public class Solution {
  2.     public boolean isNumeric(char[] str) {
  3.         int len = str.length;
  4.         boolean sign = false, decimal = false, hasE = false;
  5.         for(int i = 0; i < len; i++){
  6.             if(str[i] == '+' || str[i] == '-'){
  7.                 if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E')
  8.                     return false;
  9.                 if(sign && str[i-1] != 'e' && str[i-1] != 'E')
  10.                     return false;
  11.                 sign = true;
  12.             }else if(str[i] == 'e' || str[i] == 'E'){
  13.                 if(i == len - 1)
  14.                     return false;
  15.                 if(hasE)
  16.                     return false;
  17.                 hasE = true;
  18.             }else if(str[i] == '.'){
  19.                 if(hasE || decimal)
  20.                     return false;
  21.                 decimal = true;
  22.             }else if(str[i] < '0' || str[i] > '9')
  23.                 return false;
  24.         }
  25.         return true;
  26.     }
  27. }

13. 字符流中第一个不重复的字符

剑指offer: 字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

用一个哈希表来存储每个字符及其出现的次数，另外用一个字符串 s 来保存字符流中字符的顺序。

  1. import java.util.HashMap;
  2. public class Solution {
  3.     HashMap<Character, Integer> map = new HashMap<Character, Integer>();
  4.     StringBuffer s = new StringBuffer();
  5.     //Insert one char from stringstream
  6.     public void Insert(char ch)
  7.     {
  8.         s.append(ch);
  9.         if(map.containsKey(ch)){
  10.             map.put(ch, map.get(ch)+1);
  11.         }else{
  12.             map.put(ch, 1);
  13.         }
  14.     }
  15.   //return the first appearence once char in current stringstream
  16.     public char FirstAppearingOnce()
  17.     {
  18.         for(int i = 0; i < s.length(); i++){
  19.             if(map.get(s.charAt(i)) == 1)
  20.                 return s.charAt(i);
  21.         }
  22.         return '#';
  23.     }
  24. }
 友情链接：直通硅谷 　点职佳 　北美留学生论坛

职业生涯热门文章

  • 读哪些书可以提高思维逻辑和语言表达能力？
  • 一篇为你解读商业模式的文章
  • 2019 上半年软件设计师真题及参考答案
  • 我在华为OD的275天
  • Unity 基于 WebRTC 的云功能
  • 那些自律到极致的人，都拥有了开挂的人生
  • 那些拼命加班的程序员们，后来都怎么样了？
  • ssm整合各配置文件
  • 如何提升你在职场中的洞察力？
  • 堪比慢性自杀的习惯它排第一 你中招了吗？

    • 职业生涯推荐文章

  • 好的职场关系，都是有条件的
  • 如何有效管理高敏感的员工？
  • 记录兼职运维的一天
  • 老弟想自己做个微信，被我一个问题劝退了。。
  • 数据库与我：一段关于学习与成长的深情回顾
  • 激活员工，别讲大道理
  • 我可以写代码写到退休吗？记录我的10年前端技术之旅
  • 裸辞后，我成为全职占星师
  • 如何做笔记？
  • 我的自白书之简历

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号