[数据结构与算法 02] 回声字符串

导航

[react] Hooks

[封装01-设计模式] 设计原则 和 工厂模式(简单抽象方法) 适配器模式 装饰器模式
[封装02-设计模式] 命令模式 享元模式 组合模式 代理模式
[封装03-设计模式] Decorator 装饰器模式在前端的应用
[封装04-设计模式] Publish Subscribe 发布订阅模式在前端的应用
[封装05-ElementUI源码01] Row Col Container Header Aside Main Footer

[React 从零实践01-后台] 代码分割
[React 从零实践02-后台] 权限控制
[React 从零实践03-后台] 自定义hooks
[React 从零实践04-后台] docker-compose 部署react+egg+nginx+mysql
[React 从零实践05-后台] Gitlab-CI使用Docker自动化部署

[源码-webpack01-前置知识] AST抽象语法树
[源码-webpack02-前置知识] Tapable
[源码-webpack03] 手写webpack - compiler简单编译流程
[源码] Redux React-Redux01
[源码] axios
[源码] koa
[源码] vuex
[源码-vue01] data响应式 和 初始化渲染
[源码-vue02] computed 响应式 - 初始化，访问，更新过程
[源码-vue03] watch 侦听属性 - 初始化和更新
[源码-vue04] Vue.set 和 vm.$set
[源码-vue05] Vue.extend

[源码-vue06] Vue.nextTick 和 vm.$nextTick

[源码-react01] ReactDOM.render01
[源码-react02] 手写hook调度-useState实现

[部署01] Nginx
[部署02] Docker 部署vue项目
[部署03] gitlab-CI

[数据结构和算法01] 二分查找和排序
[数据结构和算法02] 回文字符串

[深入01] 执行上下文
[深入02] 原型链
[深入03] 继承
[深入04] 事件循环
[深入05] 柯里化 偏函数 函数记忆
[深入06] 隐式转换 和 运算符
[深入07] 浏览器缓存机制（http缓存机制）
[深入08] 前端安全
[深入09] 深浅拷贝
[深入10] Debounce Throttle
[深入11] 前端路由
[深入12] 前端模块化
[深入13] 观察者模式 发布订阅模式 双向数据绑定
[深入14] canvas
[深入15] webSocket
[深入16] webpack
[深入17] http 和 https
[深入18] CSS-interview
[深入19] 手写Promise
[深入20] 手写函数
[深入21] 数据结构和算法 - 二分查找和排序
[深入22] js和v8垃圾回收机制
[深入23] JS设计模式 - 代理，策略，单例
[深入24] Fiber
[深入25] Typescript
[深入26] Drag

[前端学java01-SpringBoot实战] 环境配置和HelloWorld服务
[前端学java02-SpringBoot实战] mybatis + mysql 实现歌曲增删改查
[前端学java03-SpringBoot实战] lombok，日志，部署
[前端学java04-SpringBoot实战] 静态资源 + 拦截器 + 前后端文件上传
[前端学java05-SpringBoot实战] 常用注解 + redis实现统计功能
[前端学java06-SpringBoot实战] 注入 + Swagger2 3.0 + 单元测试JUnit5
[前端学java07-SpringBoot实战] IOC扫描器 + 事务 + Jackson
[前端学java08-SpringBoot实战总结1-7] 阶段性总结
[前端学java09-SpringBoot实战] 多模块配置 + Mybatis-plus + 单多模块打包部署
[前端学java10-SpringBoot实战] bean赋值转换 + 参数校验 + 全局异常处理
[前端学java11-SpringSecurity] 配置 + 内存 + 数据库 = 三种方式实现RBAC
[前端学java12-SpringSecurity] JWT
[前端学java13-SpringCloud] Eureka + RestTemplate + Zuul + Ribbon

复习笔记-01
复习笔记-02
复习笔记-03
复习笔记-04

(一) 前值知识

(1) 一些单词

Palindrome 回文的

(2) 回文字符串的相关概念

1. 回文字符串的概念
- 正着和反着都相等的字符串是回文字符串
  - aba
  - abba
  - ''
  - 单个字符

(3) RegExp

var regex = /xyz/i; ------------------------ 编译时新建，效率高
等价于
var regex = new RegExp('xyz', 'i'); -------- 运行时新建，效率低
---

1. 如果正则中要使用变量，该怎么办？
- 当正则中有变量时，可以使用构造函数的方式，而不是字面量的方式
- var regex = new RegExp(`a${b}c`);



2. match

(2.1)
'abcada'.match(new RegExp('a', 'g')) // ---- ['a', 'a', 'a']
等价于 
'abcada'.match(/a/g)

(2.2)
如果match没有匹配，则返回null
'abcada'.match(/x/g) // null

(二) 判断一个字符串是不是回文字符串

(2.1) 方法1 - 反转字符串

判断一个字符串是不是回文字符串

反转字符串
- 反转字符串后，判断两个字符串是否相等
- 用于简单的判断字符串是否是回文字符串
- 不用考虑字符串是奇数还是偶数
---

const isPalindrome = (str) => {
  const reserveStr = str.split("").reverse().join("");
  return str === reserveStr;
};

(2.2) 方法2 - 双指针

判断一个字符串是不是回文字符串

双指针
- 从数组两端往中间寻找
- for
- while
---

const isPalindrome = (str) => {
  // const arr = str.split("") // 2022.04.03 注意这里其实是不需要转成数组的，字符串也可以通过下标访问到
  for(let l = 0, r= arr.length - 1; l<=r; l++, r--) {
    if (str[l] !== str[r]) return false
  }
  return true
};
---

const isPalindrome = (str) => {
  const arr = str.split("")
  let l = 0
  let r = arr.length - 1
  while(l<=r) {
    if (arr[l] !== arr[r]) return false;
    l++;
    r--;
  }
  return true
};

(1.3) 方法3 - 递归

判断一个字符串是不是回文字符串

递归
- 递归结束的条件：当传入的字符串的长度为是0或者1时，返回true
  - 因为最后长度为1，是奇数回文字符串的情况
  - 因为最后长度为0，是偶数回文字符串的情况 或者 空窜的情况
  - 长度为0或者1时，之前都是相等的才会进入递归函数，也就是说之前都是相等的，那么奇数的最后一个字符无所谓，偶数的之前一直直到知道空串时都没有不相等，说明是回文字符串
- 其实递归也是属于双指针的方式
---

const isPalindrome = (str) => {
  if (str.length <= 1) return true;
  const start = str[0]
  const end = str[str.length - 1]
  return start === end ? isPalindrome(str.slice(1, str.length -1)) : false
};

2022.04.03 更新优化如下
---

递归结束的条件
- 1. start 和 end 不相等 ------------------------------------------ 返回 false
- 2. 直到缩小到最小的范围的字符串长度是 0 或 1 时，start 和 end 都相等，----- 返回 true

function palindromicString_recursive(str) {
  const len = str.length;
  if (len <= 1) return true;
  // 如果是空字符串 或 字符串长度是1，则一定是回文字符串 ----- '' 或 '1'
  // -------------------- 递归结束条件1 ----- true

  const start = str[left];
  const end = str[str.length - 1]; // 这里使用 const 是因为每次递归都是新声明的常量，常量的值本身不会改变

  return start === end
    ? palindromicString_recursive(str.slice(1, str.length - 1)) // 每次递归都缩小范围
    : false; // -------- 递归结束条件2 ------ false
}

(三) 最长回文子串

(3.1) 暴力算法 - 三层循环

最长回文字串

暴力算法 - 三层循环
- 外面两层循环：找到所有子串
- 第三层循环：判断子串是否是回文
- 时间复杂读：( O(n^2) ) 或者 ( O(n^3)如果是三层循环的话 )
---

const maxPalindrome = (str) => {
  if (str === "") return ""; // 空字符串也是回文字符串
  if (str.length === 1) return str; // 单个字符也是回文字符串
  // 2022.04.03 其实上面两个判断是不需要的，因为上面来两种情况都在后面的写法当中了，包含了的
  
  let result = ""; // 用来缓存最长的子串，动态更新
  
  for (let i = 0; i < str.length; i++) {
    for (let j = i + 1; j <= str.length; j++) {
      // 注意：j的最大值要取到 str.length，因为slice(start, end) 是取不到end的，所以要end=str.length才可以

      const _str = str.slice(i, j); // 获取所有子串
      const _reverseStr = _str.split("").reverse().join(""); // 反转
      // 我们这里使用正反字符串对比的方式来判断是不是回文字符串
      // 当然还可以使用 双指针 循环来实现，那样就是三层循环

      if (_str === _reverseStr && _str.length > result.length) {
        // 是回文串，并且比result之前的回文串长的话，就更新较长的回文长
        result = _str;
      }
    }
  }
  return result;
};

(3.2) 动态规划算法

动态规划算法 - 前值知识

1
字符串：'abcbc'

2
三个变量：i j dp
- i 表示字符串的下标
- j 表示字符串的下标
- dp 是一个二维数组，表示 i 和 j 之间的字符串是否是回文字符串
-   `dp[i][j]` 表示string中下标i和j之间的字符串是否是回文字符串
-   `dp[0][4] = 1` 表示下标0-4之间的字符串是回文字符串
-   `dp[0][3] = 0` 表示下标0-3之间的字符串不是回文字符串

3
状态转移方程
dp[i][j] = ( string[i] === string[j] && dp[i+1][j-1] )
表示的是：
- 如果i位置的字符 和 j位置的字符相等的话，并且除去这两个字符外，这两个字符之间的字符串是一个回文字符串，那么 dp[i][j] 也是一个回文字符串，否则dp[i][j]不是一个回文字符串

4
如何实现状态转移方程
- 需要两个变量 ( len ) 和 ( result )
  - len 表示字符串的长度
  - result 表示用来记录较长的回文字符串

最长回文字串 - 动态规划 - 代码实现
---

const maxPalindrome = (str) => {
  const length = str.length;
  let result = ""; // 记录较长的回文字符串

  const dp = new Array(length)
    .fill(0)
    .map(() => new Array(length).fill(0)); 
    // 二维数组，初始值都是0，表示都不是回文字符串；length * length的二维数组
    // 初始值可以是任意值，这里使用了0，表示刚开始都不是回文字符串
    // 1 回文串
    // 0 不是回文串

  for(let len = 0; len < length; len ++) { // 遍历所有长度
    for(let i = 0; i + len < length; i++) { // 遍历所有位置的，该长度的字符；用于判断该长度的字符串是否是回文字符串; 其实就是偏移量固定，不断又偏移；这里表示可以可以偏移的最大量
      const j = i + len; // j表示右边界，i表示左边界，让取的字符串始终保持长度是len，但是i在不断的右移
      if (len === 0) dp[i][j] = 1; // 表示一个字符时，肯定是回文字符串，用1表示是回文字符串，用0表示不是回文字符串
      else if (len === 1) dp[i][j] = str[i] === str[j]; // 表示两个字符时，如果两个字符相等，是回文字符串，否则不是回文字符串
      else {
        dp[i][j] = str[i] === str[j] && dp[i+1][j-1] // 长度超过2个字符串的字符串，如果len的第一个和最后一个字符相等，并且除了这两个字符，中间的字符也是回文字符串，那么len的字符串也是回文字符串
      }

      if (dp[i][j] && len + 1 > result.length) { // len长度的回文字符串，比之前获得的最长回文字符串长的话，更新result为更长的回文字符串
        result = str.slice(i, j + 1) // 注意边界，这里 i + len + 1 也是可以的，i + len = j
      }
    }
  }

  return result
};

(四) 两个字符串的最大相同子串

1 前置知识
---

Math.min(a,b,c, ...) 
- 返回参数中的最小值
- 如果参数为空，返回 Infinity

(1) 方法1

2 原理
---

三个变量
- start ---- 表示 ( 基准字符串开始寻找相同子串的起始位置 )
- len ------ 表示 ( 两个字符串相同子串的长度 )
- temp ----- 表示在 ( 字符串str1的i位置 ) 和 ( 字符串str2的j位置 ) 上寻找到的 ( 相同字符串的长度 )

三层循环
- 第一层循环i：遍历字符串str1
- 第二层循环j：遍历字符串str2
- 第三层循环k：遍历str1和str2同时增加的寻找的部分
  - 如果 ( 字符串str1中的 i+k 位置的值 ) 和 ( 字符串str2中的 j+k 位置的值 ) 相等，则temp+1，并且如果temp > len说明有更长的子串，所以更新len和start

最后
- 返回基准串的 start，start+len 之间的子串，就是两个字符串的最长公共子串

3 代码
---

// 我们以 str1 为基准串
const maxSameStr = (str1, str2) => {
  let start = 0; // 记录相同公共子串寻找时，在基准串中的开始位置
  let len = 0; // 寻找到的公共子串的长度

  for (let i = 0; i < str1.length; i++) { // ---> 遍历所有 str1
    for (let j = 0; j < str2.length; j++) { // -> 遍历所有 str2
      let temp = 0; // temp --------------------> str1的i位置做为开始位置 和 str2的j位置做为开始位置 寻找到的相同子串的长度

      for (
        let k = 0; // k -------------------------> i和j共同向后寻找的位置
        k < Math.min(str1.length - i, str2.length - j); // 以较小的字符串，可以遍历的次数，满足木桶漏水原则
        k++
      ) {
        if (str1[i + k] === str2[j + k]) { // i和j分别向后+1寻找，两个字符相等，则temp+1
          temp++;
          if (temp > len) { // 比之前寻找的公共子串长，更新最长的子串为更大的
            len = temp;
            start = i; // 更新长度 和 起始位置，len和start成对更新，就可以截取相同子串到子串
          }
        } else {
          break; // 不相等跳出起始i和起始j的寻找，进行更新i和k后继续
        }
      }
    }
  }
  console.log(`start`, start);
  console.log(`len`, len);
  return str1.slice(start, start + len); // 计算以基准字符串str1的公共子串
};

(2) 方法2

const str1 = 'abckgf';
const str2 = 'fdbckji'

function getSame(str1, str2) {
    let result = ''
    for (let i = 0; i < str1.length; i++) {
        let temp = 0
        let tempResult = ''

        for (let j = 0; j < str2.length; j++) {
            while (str1[i + temp] === str2[j + temp] && (i+temp < str1.length || j+temp<str2.elngth)) {
                if (str1[i + temp] === str2[j + temp]) {
                    tempResult = tempResult + str1[i + temp]
                    temp++
                } else {
                    tempResult = ''
                }
            }
        }

        if (result.length < tempResult.length) {
            result = tempResult
        }
    }
    return result
}


const res = getSame(str1, str2)
console.log(res, 'res')

方法二变种
---
const str1 = "abcffddc";
const str2 = "ffddcggadfadf";

function sameStr(str1, str2) {
  let result = "";
  for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
      let temp = "";

      for (
        let k = 0;
        k < Math.min(str1.length - i, str2.length - j);
        k++
      ) {
        if (str1[i + k] === str2[j + k]) {
          temp = temp + str1[i + k];
        } else {
          break;
        }
      }

      if (result.length < temp.length) {
        result = temp;
      }
    }
  }

  return result
}

const res = sameStr(str1, str2)
console.log('res: ', res);

(五) 找出字符串中第一个只出现一次的字符

• 也叫做：找出符串中 ( 第一个 ) ( 不重复的字符 )

(5.1) map方式实现

const first = (str) => {
  const map = new Map();

  for (let i = 0; i < str.length; i++) {
    const key = str[i];
    const value = map.get(key);
    !value ? map.set(key, 1) : map.set(key, value + 1);
  }

  for (let [key, value] of map.entries()) {
    if (value === 1) {
      return key;
    }
  }

  return -1; // 都重复了返回 -1，表示都有
};

(5.2) 正则方式实现

const first = (str) => {
  for (let i of str) { // for...of可以遍历字符串，因为具有iterator接口
    const reg = new RegExp(`${i}`, "g"); // 利用构造函数，可以传入变量，因为第一个参数是字符串

    const strArr = str.match(reg);
    // match
    // - 匹配成功，返回一个数组；匹配不成功返回null
    // - 这里表示：字符串中 ( 每个相同字符 ) 组成的数组
    // - 注意：不可能匹配不到正则，因为是遍历的字符串中的字符

    if (strArr.length === 1) {
      return strArr[0]; // 第一次出现字符长度为1，直接返回该字符就是第一个只出现一次的字符
    }
  }

  return -1; // 都有重复返回 -1
};

资料

• segmentfault.com/a/119000002…
• harlanhong.github.io/posts/2020/…
• www.cxyxiaowu.com/2869.html
• 最长回文字符串 juejin.cn/post/684490…
• 最长回文马拉车 www.jianshu.com/p/9b49b5a3c…
• 第一个只出现一次的字符 blog.****.net/weixin_4316…