10 分钟掌握 BAT 面试中常考的字符串问题
下面开始今天的学习～
在 BAT 这类大公司的面试中，面试者有很大机率会被要求写一些字符串相关的题目，本文将从字符串的基础以及一些高频面试题来帮助你准备心仪公司的面试。
字符串是什么？
什么是一个字符串？在维基百科上的解释是：
字符串（英语：string），是由零个或多个字符组成的有限序列，它是编程语言中表示文本的数据类型。
一般来说，我们在 Java 中会这样看到一个字符串：
String greeting = "LeetCode is awesome!";
C++ 中可能是这样：
string greeting = "LeetCode is such awesome!";
或者简单的 Python 语句：
greeting = "LeetCode is such awesome!"
看上去是不是很简单？但在真正面试中可能就会被问到一些以上例子中不太容易想到的问题，here we go !
字符串常见面试题
回文（字符串倒置）
这是个很常见的问题，无论是学校教学还是一些简单的面试中（一般主要考察细节的处理，而非算法，因为这种操作本身没有什么太难的算法），Python 代码如下：
reversed_greeting = greeting[::-1]
如果是 C++ 的话，细节就比较多了，如果要偷懒的话可以直接使用 reverse 函数，用法如下：
reverse(greeting.begin(), greeting.end());
这样好像太偷懒了，没法展现自己的实力，不妨我们手写一个，思路就是前后对调，到字符串中点的时候停止，代码如下：
#include
using namespace std;
void reverseStr(string& str)
{
int n = str.length();
for (int i = 0; i < n / 2; i++)
swap(str[i], str[n – i – 1]);
}
int main()
{
string greeting = “LeetCode is such awesome!”;
reverseStr(greeting);
cout << greeting;
return 0;
}
怎么样，是不是感觉还是比较容易的，就是一个字符串来回变换，我们再来看看别的~
14.最长公共前缀 （点击进入）
题目描述：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
示例 1 :
示例 2 :
这就是一个比较有意思的题目了，一个比较容易的方法是从位置 0 开始，对于后续每个字符串进行一个扫描，直到遇到一个不匹配的，C++ 代码实现如下：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.empty()) return “”;
for (int idx = 0; idx < strs[0].size(); ++idx) { // 纵向扫描
for (int i = 1; i < strs.size(); ++i) {
if (strs[i][idx] != strs[0][idx]) return strs[0].substr(0,idx);
}
}
return strs[0];
}
};
或者也可以横向扫描：
class Solution {
public:
string longestCommonPrefix(vector<string> &strs) {
if (strs.empty()) return “”;
int right_most = strs[0].size() – 1;
for (size_t i = 1; i < strs.size(); i++)
for (int j = 0; j <= right_most; j++)
if (strs[i][j] != strs[0][j]) // 不会越界，请参考string::[]的文档
right_most = j – 1;
return strs[0].substr(0, right_most + 1);
}
};
替换空格
这是一个比较经典的问题，很多公司都会问到，描述如下：
将一个字符串中的每个空格替换成“%20”。例如，当字符串为 We Are Happy. 则经过替换之后的字符串为 We%20Are%20Happy.
这个题目如果用 Python 做的话，可以非常简单：
def replace(string):
lists = string.split(” “)
return ‘%20’.join(lists)
但是如果用 C++ 的话，难度就会大一些了，有一些比较成熟的解法，比如：
先遍历整个字符串，计算字符串中空格的总数，从而可以计算出替换后的字符串长度（根据替换规则，每次替换空格时，都会使字符串的长度增加2）。然后，使用两个指针或索引，从后往前遍历，即初始化指针或索引分别指向替换前和替换后字符串的末尾，循环递减，如遇到空格，则替换为 “%20″，从而减少字符串移动的次数，降低时间复杂度。
关键代码如下：
char *pChar2 = str + replacedStrLen – 1;
pChar = str + strLen – 1;
while (pChar != pChar2) {
// Replace blanks with “%20”
if (*pChar == ‘ ‘) {
pChar2 -= 2;
*pChar2 = ‘%’;
*(pChar2 + 1) = ‘2’;
*(pChar2 + 2) = ‘0’;
} else {
*pChar2 = *pChar;
}
–pChar;
–pChar2;
}
125.验证回文串 （点击进入）
题目描述：
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1 :
示例 2 :
比较容易，直接反向遍历就可以了，代码实现如下：
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;
}
}
KMP 算法
由于逐个匹配的方式效率太低，所以有了 KMP 算法，虽然一般不太会直接考到，但是由于其重要性，所以这里还是列举出来实现方法：
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
lps = [0]*M
j = 0
computeLPSArray(pat, M, lps)
i = 0 # index for txt[]
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print “Found pattern at index ” + str(i-j)
j = lps[j-1]
elif i < N and pat[j] != txt[i]:
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):
len = 0
lps[0] # lps[0] is always 0
i = 1
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
# This is tricky. Consider the example.
# AAACAAAA and i = 7. The idea is similar
# to search step.
if len != 0:
len = lps[len-1]
# Also, note that we do not increment i here
else:
lps[i] = 0
i += 1
txt = “ABABDABACDABABCABAB”
pat = “ABABCABAB”
KMPSearch(pat, txt)
看到这里，你是否对一些面试常见的字符串考点有一定的了解呢？力扣上一共有上百道 字符串 相关面试题以及探索专题，快去练练手吧！
本文作者：Nova Kwok
编辑&版式：霍霍
声明：本文归 “力扣” 版权所有，如需转载请联系。
推荐阅读
About The Author
