验证回文字符串、实现 strStr() 、最长公共前缀和最长回文子串

验证回文串

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

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

示例 1:

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

示例 2:

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

方法一

思路

首先,去除字符串中的非字母和数字,再将字符串转换为数组,再对数组首尾一一比较,即可得出结果。

详解

  1. 将传入的字符串,利用 toLowerCase() 方法统一转化为小写,再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字,最后将字符串转换为数组。

  2. 转换数组后,利用循环一一比较元素,先比较第一个和最后一个,再比较第二个和倒数二个,依次类推,若中间有不相等则不是回文串,反之,则是回文串。

代码

/**
* @param {string}
* @return {boolean}
*/
const isPalindrome = (s) => {
// 将传入的字符串,统一转化为小写,同时去除非字母和数字,在转换为数组
const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '').split('');
let i = 0;
let j = arr.length - 1;
// 循环比较元素
while (i < j) {
// 从首尾开始, 一一比较元素是否相等
if (arr[i] === arr[j]) {
// 若相等,即第二个元素和倒数第二个元素继续比较,依次类推
i += 1;
j -= 1;
} else {
// 只要有一个相对位置上不相等,既不是回文串
return false;
}
}
// 是回文串
return true;
};

复杂度分析

  • 时间复杂度:O(n)O(n) 该解法中 while 循环最多执行 n/2n/2 次,即回文时,因此,时间复杂度为 O(n)O(n)

  • 空间复杂度:O(n)O(n) 该解法中,申请了 1 个大小为 nn 的数组空间,因此,空间复杂度为 O(n)O(n)

方法二

思路

首先,去除字符串中的非字母和数字,然后,利用数组将字符串翻转,再和原字符串进行比较,即可得到结果。

详解

  1. 将传入的字符串,利用 toLowerCase() 方法统一转化为小写,再利用正则表达式 /[ ^ A-Za-z0-9]/g 在字符串中去除非字母和数字,得到字符串 arr。

  2. 将字符串 arr 转换为数组,利用数组的方法反转数组,再将数组转为字符串 newArr。

  3. 将字符串 arr 和 字符串 newArr 进行比较,相等即为回文串,不相等则不为回文串。

代码

/**
* @param {string} s
* @return {boolean}
*/
const isPalindrome = (s) => {
// 方便比较,统一转化为小写,并去除非字母和数字
const arr = s.toLowerCase().replace(/[^A-Za-z0-9]/g, '');
// 将新字符串转换为数组,利用数组的方法获得反转的字符串
const newArr = arr.split('').reverse().join('');
// 将2个字符进行比较得出结果
return arr === newArr;
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    该解法中,toLowerCase(), replace(), split(), reverse(), join() 的时间复杂度都为 O(n)O(n),且都在独立的循环中执行,因此,总的时间复杂度依然为 O(n)O(n)

  • 空间复杂度:O(n)O(n)

    该解法中,申请了 1 个大小为 nn 的字符串和 1 个大小为 nn 的数组空间,因此,空间复杂度为 O(n2)O(n*2) ,即 O(n)O(n)

实现strStr()

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。

以下称 haystack 字符串为匹配字符串,needle 字符串为查找字符串

示例

给定 haystack = 'hello world', needle = 'll'
返回2

说明:

当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

方法一 遍历截取字符串对比

思路

截取字符串对比的思路很简单,从匹配字符串 haystack 中截取出与需查找字符串 needle 长度相等的内容后,对比截取的内容与匹配字符串是否相等,如果相等返回开始截取的下标。

详解

首先处理几个特殊场景

  1. needle 的长度为0,直接返回0

  2. needle 的字符串长度大于 haystack,肯定不匹配

  3. needle 的字符串长度等于 haystack,判断是否相等,相等则匹配否则不匹配

剩下的就是 needle 字符串长度小于 haystack 的情况,遍历 haystack

此处需要注意的是,当 haystack 剩余字符串长度小于 needle 长度时,肯定是不相等,无需再次比较。

在遍历中判断 将要截取的字符串的首位与 needle 字符串的首位是否相同 ,如果不相同也就不需要后续截取、比较,跳过该次循环

代码

const strStr = function (haystack, needle) {
const hayLen = haystack.length;
const nedLen = needle.length;
if (!needle) {
return 0;
} if (nedLen > hayLen) {
return -1;
} else if (nedLen === hayLen) {
return haystack === needle ? 0 : -1;
} else {
for (let index = 0; index <= hayLen - nedLen; index++) {
if (haystack[index] !== needle[0]) {
continue;
}
if (haystack.substring(index, index + nedLen) === needle) {
return index;
}
}
}
return -1;
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

    遍历长度可能从 1 到 n1n -1,假设不同长度出现的概率均等,那么时间复杂度为 (n1+1)/2(n-1 + 1) / 2时间复杂度即为O(n)O(n)

  • 空间复杂度:O(1)O(1)

    使用 2 个额外存储空间。

方法二 双层循环对比字符

思路

循环对比字符串思路也很简单,从匹配字符串 haystack 的不同位置开始遍历,判断其中是否含有查找字符串 needle。

如:haystack 为 hello, needle 为 ll,依次判断 he、el、ll、lo是否完全和 ll 相等,相等即返回对应字符串在 haystack 中的下标。

详解

首先处理特殊边际情况,这块与第一种方法相同,就不再赘述。

以下为算法步骤:

  1. 设置最外层循环,遍历次数为 0 - haystack长度减去 needle 的长度。剩余字符串长度小于 needle 长度时,肯定不匹配

  2. 判断匹配字符串 haystack 中该次循环使用到的字符串首尾字母是否与查找字符串 needle 首尾字母相同。

    • 不相等,直接跳过继续遍历。

    • 相等,执行第三步。

  3. 判断查找字符串 needle 的长度

    • 长度为 1,表明匹配成功,直接返回当前长字符串下标即可

    • 长度大于 1,执行第四步

  4. 遍历对比字符串,循环判断匹配字符串 haystack 不同位置的字符是否与匹配字符串 needle 对应位置的字符相等

    • 不相等时,跳出循环,进行下次循环。

    • 到最后一位还未跳出循环表明完全匹配,返回当前遍历次数(即查找字符串在匹配字符串中首次出现的位置)

代码

const strStr = function (haystack, needle) {
const hayLen = haystack.length;
const nedLen = needle.length;
if (!needle) {
return 0;
} if (nedLen > hayLen) {
return -1;
} else if (nedLen === hayLen) {
return haystack === needle ? 0 : -1;
} else {
for (let hasIndex = 0; hasIndex <= hayLen - nedLen; hasIndex++) {
if (
haystack[hasIndex] === needle[0] &&
haystack[hasIndex + nedLen - 1] === needle[nedLen - 1]
) {
if (nedLen === 1) {
return hasIndex;
}
for (let nedIndex = 1; nedIndex < nedLen; nedIndex++) {
if (haystack[hasIndex + nedIndex] !== needle[nedIndex]) {
break;
}
if (nedIndex === nedLen - 1) {
return hasIndex;
}
}
}
}
}
return -1;
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    假设长字符串长度为无限大的 nn,那么对比字符串长度最大为 n1n-1,那么就需要对比 (n1)n=n2n(n-1)*n = n^2-n 次。 当 nn 趋近无限大时,n2n^2 要远远大于 nn,因此忽略减数 nn,那么时间复杂度为O(n2)O(n^2)

  • 空间复杂度:O(1)O(1)

    使用 2 个额外存储空间

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例

输入: ["flower","flow","flight"]
输出: "fl"

方法一 递归迭代

思路

查找 n 个字符串的最长公共前缀,可以拆分成两步: 1. 查找前 n-1 个字符串的最长公共前缀 m 2. 查找 m 与最后一个字符串的公共前缀

因此,我们可以得到递归公式:

$longestCommonPrefix([S1, S2, ..., Sn]) = findCommPrefix(longestCommonPrefix([S1, S2, ..., Sn-1]), Sn)$

我们只需要实现 findCommPrefix 方法,然后遍历数组即可。

详解

  1. 获取数组中第一个字符串,当做最长公共前缀保存到变量 commonPrefix

  2. 从数组中取出下一个字符串,与当前的最长公共前缀 commonPrefix 对比,得到新的最长公共前缀存到 commonPrefix

  3. 重复第 2 步遍历完整个字符串,最后得到的即使数组中所有字符串的最长公共前缀

代码

/**
* @param {string[]} strs
* @return {string}
*/
const longestCommonPrefix = function (strs) {
function findCommonPrefix (a, b) {
let i = 0;
while (i < a.length && i < b.length && a.charAt(i) === b.charAt(i)) {
i++;
}
return i > 0 ? a.substring(0, i) : '';
}
if (strs.length > 0) {
let commonPrefix = strs[0];
for (let i = 1; i < strs.length; i++) {
commonPrefix = findCommonPrefix(commonPrefix, strs[i]);
}
return commonPrefix;
}
return '';
};

复杂度分析

  • 时间复杂度:O(n)O(n)

    最坏的情况下,所有个字符串都是相同的。那么会将所有字符串的所有字符串都遍历比较一次这样就会进行 nn 次字符比较,其中 nn 是输入数据中所有字符数量。 最好的情况下,所有的字符串都不一样,那么每个字符串只会访问一次,复杂度是 nn, nn即数组长度。

  • 空间复杂度:O(1)O(1),除了保存当前公共前缀外无需其他存储空间。

方法二 循环迭代

思路

最长公共前缀一定是数组中所有数组都包含的前缀子串,我们可以将任意字符串的前缀作为公共前缀,从长度 0 到 nn (nn为该字符串长度),横向扫描数组中的所有字符串,看是否都有该前缀,直到找到不满足的为止。

详解

  1. 先假设最长公共子串的长度为 1,存到变量 ii。以第一个字符串为基准,取它的第 $i$ 个字符与数组中其他所有的字符串第 ii 个字符进行比较,如果都相等,那么将最长公共子串的长度加 1,否则停止查找,已找到最长公共前缀的长度,设置完成匹配标记 flagfalse

  2. 重复第 1 步,直到 ii 等于第一个字符串的长度,或者匹配标记 flagfalse

  3. 返回第一个字符串的前 ii 个字符,即为当前数组的最长公共前缀

代码

/**
* @param {string[]} strs
* @return {string}
*/
const longestCommonPrefix = function (strs) {
if (strs.length === 0) {
return '';
}
let i = 0;
let flag = true;
while (flag) {
if (strs[0].length > i) {
const char = strs[0].charAt(i);
for (let j = 1; j < strs.length; j++) {
if (strs[j].length <= i || strs[j].charAt(i) !== char) {
flag = false;
break;
}
}
} else {
flag = false;
}
i++;
}
return strs[0].substring(0, i - 1);
};

复杂度分析:

  • 时间复杂度:O(n)O(n)

  • 空间复杂度:O(1)O(1)

    整个过程只需要存储匹配标志。

最长回文子串

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

示例

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

方法一 动态规划法

思路

动态规划的思想,是希望把问题划分成相关联的子问题;然后从最基本的子问题出发来推导较大的子问题,直到所有的子问题都解决。

根据字符串的长度,建立一个矩阵 dp, 通过不同情况的判断条件,通过 dp[i][j] 表示 s[i] 至 s[j] 所代表的子串是否是回文子串。

详解

  1. 建立矩阵 dp

  2. 循环遍历字符串,取得不同长度的子串

  3. 不同长度的子串,根据不同的条件进行判断是否为回文子串

    (1)长度为 1,一定回文

    (2)长度为 2 或 3,判断首尾是否相同:s[i] === s[j]

    (3)长度 > 3, 首尾字符相同,且去掉首尾之后的子串仍为回文:(s[i] === s[j]) && dp[i + 1][j - 1]

  4. 取得长度最长的回文子串

/**
* @param {string} s
* @return {string}
*/
const longestPalindrome = function (s) {
const dp = [];
for (let i = 0; i < s.length; i += 1) {
dp[i] = [];
}
let max = -1; let str = '';
for (let l = 0; l < s.length; l += 1) {
// l为所遍历的子串长度 - 1,即左下标到右下标的长度
for (let i = 0; i + l < s.length; i += 1) {
const j = i + l;
// i为子串开始的左下标,j为子串开始的右下标
if (l === 0) {
// 当子串长度为1时,必定是回文子串
dp[i][j] = true;
} else if (l <= 2) {
// 长度为2或3时,首尾字符相同则是回文子串
if (s[i] === s[j]) {
dp[i][j] = true;
} else {
dp[i][j] = false;
}
} else {
// 长度大于3时,若首尾字符相同且去掉首尾之后的子串仍为回文,则为回文子串
if ((s[i] === s[j]) && dp[i + 1][j - 1]) {
dp[i][j] = true;
} else {
dp[i][j] = false;
}
}
if (dp[i][j] && l > max) {
max = l;
str = s.substring(i, j + 1);
}
}
}
return str;
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2) 遍历次数取决于字符串的长度,因为是两层循环嵌套,所以遍历的最大次数为 n2n^2

  • 空间复杂度:O(n)O(n)需要申请空间为字符串长度 nn 的数组来记录不同长度子串的情况。

方法二 中心扩展

思路

回文子串一定是对称的,所以我们可以每次选择一个中心,然后从中心向两边扩展判断左右字符是否相等。

中心点的选取有两种情况:

当长度为奇数时,以单个字符为中心;

当长度为偶数时,以两个字符之间的空隙为中心。

详解

1.循环遍历字符串取得不同长度的子串

2.通过定义好的中心扩展方法,选取奇数对称和偶数对称的中心

3.通过比较选择出两种组合较大的回文子串长度,然后对比之前的长度,判断是否更新起止位置

4.全部遍历完成后,根据最后的起止位置的值,截取最长回文子串

/**
* @param {string} s
* @return {string}
*/
const longestPalindrome = function (s) {
if (s == null || s.length < 1) {
return '';
}
let start = 0; let end = 0;
// 从中心向两边扩展
const expandFromCenter = (s, left, right) => {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left -= 1;
right += 1;
}
return right - left - 1;
};
for (let i = 0; i < s.length; i += 1) {
// 中心的两种选取(奇对称和偶对称)
const len1 = expandFromCenter(s, i, i);
const len2 = expandFromCenter(s, i, i + 1);
// 两种组合取最大的回文子串长度
const len = Math.max(len1, len2);
// 如果此位置为中心的回文数长度大于之前的长度,则进行处理
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
};

复杂度分析

  • 时间复杂度:O(n2)O(n^2)

    遍历次数取决于字符串的长度,因为是两层循环嵌套,所以遍历的最大次数为 n2n^2

  • 空间复杂度:O(1)O(1)

    只使用到常数个临时变量,与字符串长度无关。