大家好,我是「柒八九」。一个立志要成为「海贼王的男人」。
今天,我们讲一讲,JS中针对 String
类型的相关算法的解题技巧和一些注意事项。
我们之前,已经有3篇文章,从不同视角来探寻JS算法中可能遇到的「礁石」。如果有诸君需要的,「拿走不谢」,但是不要忘记回来,看下面的文章。
天不早了,我们干点正事哇。
counts = new Array(x).fill(0)
s.charAt(i).charCodeAt()
++
或--
i-s1l
,第二指针i
left=0
/right= s.length-1
i
可为奇数中心,i
与i+1
可为偶数中心每个字符在 JS 内部都是以16位(即「2个字节」)的 UTF-16
格式储存,也就是说 「JS 的字符长度固定为16位长度,即2个字节」
❝
ECMAScript
中的String
是「不可变的」即:「String一旦创建,他们的值就不能改变」 ❞
要改变某个变量保存的String
,首先要「销毁原来的」 String
,然后再用另一个「包含新值的」 String
填充该变量。
let stringVal = '北宸';
stringVal = stringVal + '南蓁';
实现这个操作的过程如下:
❝在JS中,「字符串可以被视为字符数组」 ❞
str.charAt(i)
用于获取str
在i
位置的字符在JS中,字符之间是无法之间「相减」
'b' - 'a' // NAN
其实,这里面的深层次的原因是,JS中针对 '-'操作符,没兼容字符。而-
操作符要的预期就是返回数值,因为,字符没被兼容,所以结果返回了一个NAN
。
作为替换方案,str.charAt(i).charCodeAt()
(获取str
在i
位置的字符ASCLL
码值 )就肩负起,字符之间相减的操作
str = 'ba';
str.charAt(1).charCodeAt() - str.charAt(0).charCodeAt()
// 结果为1 b的ascll 为98,a的ascll为97 即:98 -97
在JS算法探险之数组中我们通过「双指针」的技巧,来处理一些比较有特点的数组数据。
「字符串可以被视为字符数组」,那么也可以用「双指针」的技巧来处理字符串的一些问题。
由于在处理字符串时,很多都与「统计字母出现的次数有关」,所以我们可以借用「哈希表」(map)来存储每个元素出现的次数。
❝Map 在信息存储方面还是很有用的。在讲「数组」算法中,在非正整数用Si时,就用 Map进行key 和value的信息存储 ❞
题目描述:
❝输入字符串s1和s2,判断s2中是否包含s1的某个变位词 提示: 如果s2中包含s1的某个变位词,则s1至少有一个变位词是s2的「子字符串」 假设两个字符串中只包含英文小写字母 示例:s1 为“ac”, s2为“dgcaf” ,由于s2包含s1的变位词"ca", 结果为「true」 ❞
a
, 下标为1对应字母b
s1
,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
s2
的「子字符串」是否包含s1
的变位词s1
长度为n
s2
中「长度为n
的子字符串」是不是s1
的变位词-1
s1
的变位词function checkInclusion(s1,s2){
let s1l = s1.length,s2l = s2.length;
if(s2l<s1l) return false;
// 构建 字符 => 个数 数组
let counts = new Array(26).fill(0);
// 遍历s1,并对s1中字符进行数据收集 (++)
// 针对已收集的s1数据信息,与s2进行匹配(--)
for(let i =0;i<s1l;i++){
counts[s1.charAt(i).charCodeAt() - 97]++;
counts[s2.charAt(i).charCodeAt() - 97]--;
}
//判断,是否全为0,如果是,刚才已经满足情况了,直接返回true
if(areaAllZero(counts)) return true;
//从s1l的位置出发,先匹配,后收集(类似同向双指针)
for(let i = s1l;i<s2l;i++){
counts[s2.charAt(i).charCodeAt() - 97]--;
counts[s2.charAt(i - s1l).charCodeAt() -97]++;
if(areaAllZero(counts)) return true;
}
return false
}
辅助函数,用于判断,数值中值是否都为0
function areaAllZero(counts){
for(let count of counts) {
if(count >0) return false
}
return true;
}
在上面的函数中,
i-s1l
的位置i
相当于「第二个指针」,指向「子字符串」的最后一个字符s1
的长度题目描述:
❝输入字符串s1和s2,找出s1的「所有」变位词在s1中的「起始」下标 提示: 假设两个字符串中只包含英文小写字母 示例:s1 为“abc”, s2为“cbadabacg” ,s1的两个变位词"cba"/"bac"是
s1
中的子字符串,输出在s1
中的起始下标为0和5 ❞
和找「字符串中的变位词」的思路是一样的
a
, 下标为1对应字母b
s1
,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
s2
的「子字符串」是否包含s1
的变位词s1
长度为n
s2
中「长度为n
的子字符串」是不是s1
的变位词-1
s1
的变位词(进行下标的记录处理)function findAnagrams(s1,s2){
let result = [];
let s1l = s1.length,s2l = s2.length;
if(s2l<s1l) return result;
let counts = new Array(26).fill(0);
for(let i= 0;i<s1l;i++){
counts[s1.charAt(i).charCodeAt() - 97]++;
counts[s2.charAt(i).charCodeAt() - 97]--;
}
if(areaAllZero(counts)) result.push(0);
for(let i= s1l;i<s2l;i++){
counts[s2.charAt(i).charCodeAt()-97]--;
counts[s2.charAt(i-s1l).charCodeAt()-97]++;
// 在满足情况下,对应的开始下标为`i-s1l+1`
if(areaAllZero(counts)) result.push(i - s1l+1);
}
return result
}
辅助函数,用于判断,数值中值是否都为0
function areaAllZero(counts){
for(let count of counts) {
if(count >0) return false
}
return true;
}
针对「字符串中的变位词」还是「字符串中所有变位词」中用到的思路,都是「利用数组来模拟哈希表」(map)然后,针对特定的场景进行数据的处理。然后,针对双指针的定义,在第二个for
循环中,第一个指针为i-s1l
对应的位置,第二个指针,为i
对应的位置,而两者恰好相差(s1l)的长度。
题目描述:
❝输入一个字符串,求该字符串中不含重复字符的「最长子字符串」 示例: 输入"babcca",其最长的不含重复字符的子字符串为“abc”,长度为3 ❞
new Array(256).fill(0)
function lengthOfLongestSubstring(s){
let sl = s.length;
if(sl==0) return 0;
let counts = new Array(256).fill(0);
let longest = 0;
let j= -1; // 左指针
// i 为右指针
for(let i=0;i<sl;i++){
counts[s.charAt(i).charCodeAt()]++;
while(hasGreaterThan1(counts)){
j++
counts[s.charAt(j).charCodeAt()]--;
}
// 更新最长子串的长度
longest = Math.max(i-j,longest);
}
return longest;
}
辅助函数,用于判断数组中是否有含有大于1的数
function hasGreaterThan1(counts){
for(let count of counts){
if(count>1) return true
}
return false;
}
在上面代码中,其实难点就是双指针的定义和赋值
hasGreaterThan1
为true时,j++
,且counts
指定位置counts[s.charAt(j).charCodeAt()]--
回文是一类特殊的字符串。不管「从前往后」,还是「从后往前」,得到的字符信息都是一样的。
题目描述:
❝输入一个字符串,判断它是不是回文 提示: 只考虑字母和数字字符,忽略大小写 示例: 输入字符串“abba”返回true, 输入“abc”返回false ❞
function isPalindrome(s){
let left =0,right = s.length -1;
while(left<right){
// 获取指定位置的字符
let cl = s.charAt(left);
let cr = s.charAt(right);
// 跳过非数字和字母的字符 (!isLetterOrDigit(x))
if(!isLetterOrDigit(cl)){
left++;
}else if(!isLetterOrDigit(cr)){
right--;
}else {
// 大小写不敏感
cl = cl.toLocaleLowerCase();
cr = cr.toLocaleLowerCase();
// 不一样,跳出循环
if(cl!=cr) return false
// 指针移动
left++;
right--;
}
}
return true;
}
辅助函数
const isLetterOrDigit = str => /^[A-Za-z0-9]+$/.test(str)
题目描述:
❝输入一个字符串,判断「最多」从字符串中删除一个字符能不能得到一个回文字符串 示例: 输入字符串“abca”, 删除字符
b
或者c
能得到一个回文字符串,因此输出true ❞
function validPalindrome(s){
let left =0,right = s.length -1;
let middlePosition = s.length>>1;
// 移动指针,并比较字符是否相等
for(;left<middlePosition;left++,right--){
if(s.charAt(left)!=s.charAt(right)) break;
}
// 这里有两类情况
// 1: 字符串本身是回文 (left == middlePosition)
// 2. 需要对字符串进行字符剔除 (isPalindrome)
return left == middlePosition
|| isPalindrome(s,left,right-1)
|| isPalindrome(s,left+1,right)
}
辅助函数,用于判断字符串是否是回文
function isPalindrome(s,left,right){
while(left<right){
if(s.charAt(left)!= s.charAt(right)) break;
left++;
right--;
}
return left>=right;
}
这里有一个比较重要的点,就是「最多」可以删除一个字符。放到代码中其实就是在validPalindrome
中return
那里体现
validPalindrome
中for
循环没阻断,即:left == middlePositon
validPalindrome
中的for
发生了「阻断」(break)isPalindrome(s,left,right-1)
isPalindrome(s,left+1,right)
题目描述:
❝输入一个字符串,求字符串中有多少个「回文连续子字符串」? 示例: 输入字符串“abc”有3个回文子字符串,分别是"a"/"b"/"c" ❞
function countSubstrings(s){
if(s==null || s.length==0) return 0; //处理边界
let count = 0;
for(let i=0;i<s.length;i++){
// 字符串下标为i。
// 既作为奇数回文的中心
// 又可以和i+1一同作为偶数回文的中心
count+=countPalindrome(s,i,i);
count+=countPalindrome(s,i,i+1);
}
return count;
}
辅助函数,
function countPalindrome(s,left,right){
let count = 0;
while(left>=0&&right<s.length
&& s.charAt(left)==s.charAt(right)){
count++;
left--;
right++;
}
return count;
}
这个题,最主要的就是需要明白:
i
个字符本身可以成为「长度为奇数」的回文字符串的对称中心i
的位置 countPalindrome(s,i,i);
i
个字符和第i+1
个字符可以成为「长度为偶数」的回文字符串的对称中心i
的位置 countPalindrome(s,i,i+1);
「分享是一种态度」。
参考资料:剑指offer