几道 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"。
在处理的时候去优先寻找更短的回文串,然后回溯找稍微长一些的回文串分割方法,不断回溯,分割,直到找到所有的分割方法。
举个
©著作权归作者所有:来自51CTO博客作者mb5fe18fab305a5的原创作品,如需转载,请注明出处,否则将追究法律责任更多相关文章
- 动画:回文数的三种解法 | 法解种三的数文回:画动
- 字符串处理函数
- PHP中字符串处理的一些常用函数
- php字符串处理函数分类(优秀推荐)
- PHP字符串变量介绍
- PHP去掉字符串中的“#”
- substr函数在php中截取部分字符串(附详解)
- php base64如何进行URL字符串编码和解码?
- 解析PHP vsprintf()函数格式化字符串操作原理