JS算法探险之字符串

简介: 双指针 回文字符串
+关注继续查看


离每个人最远的,就是他自己  --尼采

大家好,我是柒八九。一个立志要成为海贼王的男人

今天,我们讲一讲,JS中针对 String类型的相关算法的解题技巧和一些注意事项。

我们之前,已经有3篇文章,从不同视角来探寻JS算法中可能遇到的礁石。如果有诸君需要的,拿走不谢,但是不要忘记回来,看下面的文章。

::: block-1

文章list

天不早了,我们干点正事哇。 image


::: block-1

字符串-打油诗

  • 字符串算法有很多,变位词回文串来报道
  • 变位词要数数哈希表来撑场面
    • 哈希表可变通,counts = new Array(x).fill(0)
    • 下标对应ascll字符,s.charAt(i).charCodeAt()
    • 值对应字符梳理, counts[x]++--
    • 反向双指针,第一指针,始终为i-s1l,第二指针i
  • 回文串有特点,前后字符都一样
    • 反向双指针花样多
    • 两边向中间,left=0/right= s.length-1
    • 中间向两边, i可为奇数中心,ii+1可为偶数中心 :::

文章概要

  1. 双指针
  2. 回文字符串

知识点简讲

String本质

每个字符在 JS 内部都是以16位(即2个字节)的 UTF-16 格式储存,也就是说 JS 的字符长度固定为16位长度,即2个字节

ECMAScript 中的String不可变的即:String一旦创建,他们的值就不能改变

要改变某个变量保存的String,首先要销毁原来的 String,然后再用另一个包含新值的 String填充该变量。

let stringVal = '北宸';
stringVal = stringVal + '南蓁';
复制代码

实现这个操作的过程如下:

  1. 创建一个能容纳8个字节的新String
  2. 在这个String中填充 "北宸"和"南蓁"
  3. 销毁原来的String "北宸"和"南蓁"

工具方法 & 语言特性

在JS中,字符串可以被视为字符数组

  • str.charAt(i)
    用于获取stri位置的字符

在JS中,字符之间是无法之间相减

'b' - 'a' // NAN
复制代码

其实,这里面的深层次的原因是,JS中针对 '-'操作符,没兼容字符。而-操作符要的预期就是返回数值,因为,字符没被兼容,所以结果返回了一个NAN

作为替换方案,str.charAt(i).charCodeAt()(获取stri位置的字符ASCLL码值 )就肩负起,字符之间相减的操作

str = 'ba';
str.charAt(1).charCodeAt() - str.charAt(0).charCodeAt()
// 结果为1  b的ascll 为98,a的ascll为97 即:98 -97 
复制代码

1. 双指针

JS算法探险之数组中我们通过双指针的技巧,来处理一些比较有特点的数组数据。

字符串可以被视为字符数组,那么也可以用双指针的技巧来处理字符串的一些问题。

由于在处理字符串时,很多都与统计字母出现的次数有关,所以我们可以借用哈希表(map)来存储每个元素出现的次数。

Map 在信息存储方面还是很有用的。在讲数组算法中,在非正整数用Si,就用 Map进行key 和value的信息存储

字符串中的变位词

题目描述:

输入字符串s1和s2,判断s2中是否包含s1的某个变位词 

提示: 

如果s2中包含s1的某个变位词,则s1至少有一个变位词是s2的子字符串

假设两个字符串中只包含英文小写字母 


示例:s1 为“ac”, s2为“dgcaf” ,由于s2包含s1的变位词"ca", 结果为true

::: block-1

分析

  1. 变位词是指组成各个单词的字母及每个字母出现的次数完全相同,只是字母的排列顺序不同
  2. 变位词有几个特点
    • 一组变位词长度相同
    • 组成变位词的字母集合相同
    • 每个字母出现的次数也相同
  1. 变位词与字母及字母出现的次数有关,那么统计字符串中包含的字母及每个字母出现的次数。
    • 哈希表的是字母
    • 对应的是字母出现的次数
  1. 题中,说只含有小写英文,所以我们可以用数组模拟一个哈希表
    • 数组下标表示字母,即 下标为0 对应字母a, 下标为1对应字母b
    • 数组中的表示对应字母出现的次数
  1. 首先,扫描s1,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
  2. 判断s2子字符串是否包含s1的变位词
    • 假设s1长度为n
    • 逐一判断s2长度为n的子字符串是不是s1的变位词
    • 扫描子字符串中的每个字母,把该字母在哈希表中对应的值-1
    • 如果哈希表中所有值都是0,那么该子字符串就是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的位置
  • 第二个for循环中的下标i相当于第二个指针,指向子字符串的最后一个字符
  • 两个指针之间的子字符串的长度一直是字符串s1的长度

字符串中所有变位词

题目描述:

输入字符串s1和s2,找出s1的所有变位词在s1中的起始下标 

提示: 

假设两个字符串中只包含英文小写字母 


示例:s1 为“abc”, s2为“cbadabacg” ,s1的两个变位词"cba"/"bac"是s1中的子字符串,输出在s1中的起始下标为0和5

::: block-1

分析

和找字符串中的变位词的思路是一样的

  1. 变位词与字母及字母出现的次数有关,那么统计字符串中包含的字母及每个字母出现的次数。
    • 哈希表的是字母
    • 对应的是字母出现的次数
  1. 题中,说只含有小写英文,所以我们可以用数组模拟一个哈希表
    • 数组下标表示字母,即 下标为0 对应字母a, 下标为1对应字母b
    • 数组中的表示对应字母出现的次数
  1. 首先,扫描s1,每扫描到一个字符,就找到它在哈希表中的位置,并把它对应+1
  2. 判断s2子字符串是否包含s1的变位词
    • 假设s1长度为n
    • 逐一判断s2长度为n的子字符串是不是s1的变位词
    • 扫描子字符串中的每个字母,把该字母在哈希表中对应的值-1
    • 如果哈希表中所有值都是0,那么该子字符串就是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

::: block-1

分析

  1. 此处用哈希表(map)统计子字符串中字符出现的次数
  2. 如果一个字符串中不含重复的字符,那么每个字符都是只出现一次,即哈希表中对应的值为1
  3. 我们还是采用用数组来模拟哈希表,由于题目中,没限制字符为小写英文字母,所以我们需要对字符做一个简单限制,只处理ascll的字符,即:new Array(256).fill(0)
  4. 仍用两个指针来定位一个子字符串
    • 第一个指针指向子字符串的第一个字符
    • 第二个指针指向子字符串的最后一个字符
  1. 如果两个指针之间的子字符串不包含重复的字符,为了找出最长的子字符串,向右移动第二个指针,然后判断是否出现重复字符
  2. 如果两个指针之间的子字符串中包含重复的字符,向右移动第一个指针

:::

代码实现

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;
}
复制代码

在上面代码中,其实难点就是双指针的定义和赋值

  • 左指针
    1. 默认值为-1
    2. 在hasGreaterThan1为true时,j++,且counts指定位置counts[s.charAt(j).charCodeAt()]--
  • 右指针
    1. 默认值为0
    2. 通过循环控制右指针移动

回文字符串

回文是一类特殊的字符串。不管从前往后,还是从后往前,得到的字符信息都是一样的。

有效回文


题目描述:

输入一个字符串,判断它是不是回文 

提示: 

只考虑字母和数字字符,忽略大小写 


示例: 输入字符串“abba”返回true, 输入“abc”返回false

::: block-1

分析

  1. 判断字符串是否为回文,既定套路反向双指针
    • 一个指针从第一个字符开始,从前往后移动
    • 另一个指针从最后一个字符开始,从后往前移动
  1. 针对非数字和字母的字符,进行跳过处理
  2. 大小写需要转换

:::

代码实现

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

::: block-1

分析

  1. 判断字符串是否为回文,既定套路反向双指针
    • 一个指针从第一个字符开始,从前往后移动
    • 另一个指针从最后一个字符开始,从后往前移动
  1. 题目中说,最多删除一个字符
    • 不删除: 本身就是回文串
    • 删除:可能是前半部分,也可能是后半部分

:::

代码实现

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;
}
复制代码

这里有一个比较重要的点,就是最多可以删除一个字符。放到代码中其实就是在validPalindromereturn那里体现

  • 不删除字符: 本身就是回文,那就意味着在validPalindromefor循环没阻断,即:left == middlePositon
  • 删除字符: 意味着在validPalindrome中的for发生了阻断(break)
    • 在阻断处,删除后半部分的字符isPalindrome(s,left,right-1)
    • 在阻断处,删除前半部分的字符isPalindrome(s,left+1,right)

回文子字符串的个数

题目描述:

输入一个字符串,求字符串中有多少个回文连续子字符串? 


示例: 输入字符串“abc”有3个回文子字符串,分别是"a"/"b"/"c"

::: block-1

分析

  1. 判断字符串是否为回文,既定套路反向双指针
    • 从两边向中间移动(比较常见)
    • 从中间向两边扩散
  1. 回文的长度既可以是奇数,也可以是偶数
    • 长度为奇数的回文的对称中心只有一个字符
    • 长度为偶数的回文的对称中心有两个字符

:::

代码实现

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

全文完,既然看到这里了,如果觉得不错,随手点个赞和“在看”吧。

image


相关文章
|
1月前
|
算法 Java 程序员
【手绘算法】力扣 3 无重复的最长字符串(Longest Substring Without Repeating Characters)
Hi,大家好,我是Tom。一个美术生转到Java开发的程序员。今天给大家分享的是力扣题第3题,无重复的最长字符串。在解题过程中,也会手写一些伪代码。当然,如果想要完整的源码的话,可以到我的个人主页简介中获取。 这道题呢属于中等难度,评估为四颗星,它的通过率只有39%。
23 0
|
2月前
|
算法
算法练习Day56|583. 两个字符串的删除操作 ● 72. 编辑距离
算法练习Day56|583. 两个字符串的删除操作 ● 72. 编辑距离
|
2月前
|
算法 索引
代码随想录算法训练营第八天 | 344.反转字符串541. 反转字符串II 剑指Offer 05.替换空格151.翻转字符串里的单词剑指Offer58-II.左旋转字符串
代码随想录算法训练营第八天 | 344.反转字符串541. 反转字符串II 剑指Offer 05.替换空格151.翻转字符串里的单词剑指Offer58-II.左旋转字符串
|
2月前
|
算法 Java API
字符串的匹配算法【学习算法】
字符串的匹配算法【学习算法】
19 1
|
2月前
|
存储 算法
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
算法之字符串问题(第415题字符串相加、第43题字符串相乘、第316题去除重复字母)
14 0
|
2月前
|
算法 测试技术
算法强化每日一题--字符串中找出连续最长的数字串
算法强化每日一题--字符串中找出连续最长的数字串
|
2月前
|
算法 测试技术
算法强化每日一题--倒置字符串
算法强化每日一题--倒置字符串
|
3月前
|
算法
【算法】手摇算法反转部分字符串
【算法】手摇算法反转部分字符串
22 0
|
3月前
|
存储 算法 Java
带你刷算法——数组/字符串的完全掌握(一)(下)
带你刷算法——数组/字符串的完全掌握(一)
|
3月前
|
存储 算法 Java
带你刷算法——数组/字符串的完全掌握(一)(中)
带你刷算法——数组/字符串的完全掌握(一)
热门文章
最新文章
相关产品
机器翻译
推荐文章
更多