js 算法问题解决（第 6 天） - LeetCode：680. 验证回声字符串 Ⅱ 和 28. 实现 strStr

「这是我参与2022首次更文挑战的第7天，活动详情查看：2022首次更文挑战」

前言

每天至少一道算法题，死磕算法

今天我们来讲一下验证回文字符串的进阶版，验证回文字符串II，一看II呀，III呀这些字，那就是前一题进阶版，只需要在前一题的基础上加上一两步运算就可以了

题目

这是leetcode上的第680道题

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

难度：简单(看道这道题难度简单，心里乐呵呵)

示例 1:

输入: s = "aba"
输出: true

思路

从题目中提取关键字

• 1.给定一个非空字符串，所以我们不用判断这个字符串是空的
• 2.最多删除一个字符，判断是否能成为为回文串

分析

• 1.我们可以先写一个判断是否是回文串的函数
• 2.如果给定的字符串已经是回文串了，我们直接返回true
• 3.如果给定的字符串不是回文串的话，那么我们可以用双指针(想必看了前面文章的小伙伴，对双指针掌握的都比较熟练了)判断哪两个字符不对称，当发现不对称的字符以后
  • 1.left+1,判断剩余的字符串是否是回文串
  • 2.right-1，判断剩余的字符串是否是回文串
  • 3.如果两个字符串有一个是回文串的话，那么整个字符串就是回文串，如果两个都不是回文串的话，那么整个字符串都不是回文串

注意：

• 此处一定要注意substring方法的使用,他不包括最后一个元素
• 还会使用到前面做过的isPalindrome题目，直接判断是否是回文串

题解

/**
 * @param {string}
 * @return {boolean}
 */
var isPalindrome = function (s) {
  // 我们先对字符串进行一下处理，只留下字母和数字
  return s === s.split("").reverse().join("");
};

var validPalindrome = function (s) {
  if (isPalindrome(s)) {
    return true;
  }
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) {
    // 记住我们只能删除一个字符
      return (
        isPalindrome(s.substring(left + 1, right+1)) ||
        isPalindrome(s.substring(left, right))
      );
    } else {
      left++;
      right--;
    }
  }
};

我们再来一道字符串题，巩固一下

题目

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：

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

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

难度：简单

示例 1：

输入： haystack = "hello", needle = "ll"
输出： 2

思路

从题目中提取关键词

• 1.strStr函数相当于js的indexOf函数，想必大家都用过indexOf函数
• 2.找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
• 3.如果传入的字符串是空的话，那么返回0

分析

• 1.我们可以先写一个判断字符串是否相等的函数
• 2.如果needle为空的话，直接返回0
• 3.如果haystack.length < needle.length,直接返回-1
• 4.我们遍历haystack字符串，从haystack和needle第一个字符开始对比
  • 1.如果有相同的字符，则根据needle的长度截取haystack，然后判断与needle是否相等
    • 1.如果相等，则返回上指针的索引
    • 2.如果不相等，则left+1;
  • 2.如果字符不相同，则left+1;
• 5.如果上面的遍历没有相等的字符，则返回-1；

虽然上面的思路比较长，但是还是很清晰的

题解

/**

* @param {string} haystack

* @param {string} needle

* @return {number}

*/
//判断字符串是否相等
var isSameStr = function (str, needle) {
 return str === needle;
};


var strStr = function (haystack, needle) {
    // 定义左指针
    let left = 0;
    while (left < haystack.length) {
        if (haystack[left] === needle[0]) {
            if (isSameStr(haystack.substring(left, left + needle.length), needle)) {
                return left;
            } else {
                left++;
            }
        } else {
            left++;
        }
    }
    return -1;
};

总结

今天已经算法第六天了，努力，加油，坚持就是胜利✌????

参考

• 680. 验证回文字符串 Ⅱ - 力扣（LeetCode）
• 28. 实现 strStr()