D071a4859412298a235b3a2e3b14ff89
几道 BAT 算法面试中经常问的「字符串」问题

String 作为最常见的编程语言类型之一,在算法面试中出现的频率极高。

1. 验证回文串

题目来源于 LeetCode 第 125 号问题:验证回文串。这道题目是 初级程序员 在面试的时候经常遇到的一道算法题,而且面试官喜欢面试者手写!

题目描述

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

题目解析

先理解一个概念:所谓回文,就是一个正读和反读都一样的字符串。

先假设是验证单词 level 是否是回文字符串,通过概念涉及到 正 与 反 ,那么很容易想到使用双指针,从字符的开头和结尾处开始遍历整个字符串,相同则继续向前寻找,不同则直接返回 false。

而这里与单独验证一个单词是否是回文字符串有所区别的是加入了 空格 与 非字母数字的字符,但实际上的做法一样的:

一开始先建立两个指针,left 和 right , 让它们分别从字符的开头和结尾处开始遍历整个字符串。

如果遇到非字母数字的字符就跳过,继续往下找,直到找到下一个字母数字或者结束遍历,如果遇到大写字母,就将其转为小写。

当左右指针都找到字母数字时,可以进行比较的时候,比较这两个字符,如果相等,则两个指针向它们的前进方向挪动,然后继续比较下面两个分别找到的字母数字,若不相等,直接返回 false。

动画描述

动画描述

动画描述

代码实现

注:isLetterOrDigit 方法确定指定的字符是否为字母或数字。

class Solution {
    public boolean isPalindrome(String s) {
        if(s.length() == 0)
             return true;
        int l = 0, r = s.length() - 1;
        while(l < r){
            //确定指定的字符是否为字母或数字
            if(!Character.isLetterOrDigit(s.charAt(l))){
                l++;
            }else if(!Character.isLetterOrDigit(s.charAt(r))){
                r--;
            }else{
                if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
                    return false;
                l++;
                r--;
            } 
        }
        return true;
    }
}

2. 分割回文串

题目来源于 LeetCode 第 131 号问题:分割回文串。

题目描述

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

题目解析

首先,对于一个字符串的分割,肯定需要将所有分割情况都遍历完毕才能判断是不是回文数。不能因为 abba 是回文串,就认为它的所有子串都是回文的。

既然需要将所有的分割方法都找出来,那么肯定需要用到DFS(深度优先搜索)或者BFS(广度优先搜索)。

在分割的过程中对于每一个字符串而言都可以分为两部分:左边一个回文串加右边一个子串,比如 "abc" 可分为 "a" + "bc" 。 然后对"bc"分割仍然是同样的方法,分为"b"+"c"。

在处理的时候去优先寻找更短的回文串,然后回溯找稍微长一些的回文串分割方法,不断回溯,分割,直到找到所有的分割方法。

举个🌰:分割"aac"。

  1. 分割为 a + ac
  2. 分割为 a + a + c,分割后,得到一组结果,再回溯到 a + ac
  3. a + ac 中 ac 不是回文串,继续回溯,回溯到 aac
  4. 分割为稍长的回文串,分割为 aa + c 分割完成得到一组结果,再回溯到 aac
  5. aac 不是回文串,搜索结束

动画描述

动画描述

动画描述

代码实现

```java
class Solution {
List> res = new ArrayList<>();

public List<List<String>> partition(String s) {
    if(s==null||s.length()==0)
        return res;
    dfs(s,new ArrayList<String>(),0);
    return res;
}

public void dfs(String s,List<String> remain,int left){
    if(left==s.length()){  //判断终止条件
        res.add(new ArrayList<String>(remain));  //添加到结果中
        return;
    }
    for(int right=left;right<s.length();right++){  //从left开始,依次判断left->right是不是回文串
        if(isPalindroom(s,left,right)){  //判断是否是回文串
            remain.add(s.substring(left,right+1));   //添加到当前回文串到list中
            dfs(s,remain,right+1);  //从right+1开始继续递归,寻找回文串
            remain.remove(remain.size()-1);  //回溯,从而寻找更长的回文串
        }
    }
}
/**
* 判断是否是回文串
*/
public boolean isPalindroom(String s,int left,int right){
    while(left<right&&s.charAt(left)==s.charAt(right)){
        left++;
        right--;
    }
    return left>=right;
}
top Created with Sketch.