【面试经典150 | 双指针】验证回文串

这篇具有很好参考价值的文章主要介绍了【面试经典150 | 双指针】验证回文串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【双指针】【回文串】【字符串】


题目来源

125. 验证回文串

【面试经典150 | 双指针】验证回文串,面试经典150题,双指针,回文串,字符串

题目解读

给你一个字符串 s,该字符串包含的字符由 ASCII 字符组成。如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。请判断字符串 s 是否是回文串。


解题思路

对于本题可以有两种处理方法,一是先将字符换 s 中的字母字符筛选出来并将存储小写形式到临时变量 str 中,再对 str 进行回文串判断;而是直接对字符串 s 进行原地判断。

方法一:筛选+判断

对于筛选,别无二法,进行一次遍历,对遍历到的字符判断是否是字母或者数字,如果是,则将小写形式存放入 str 中。

判断回文有两种方法,一种是借助 API 对字符串逆序,将得到的逆序字符串与原字符串进行比较,如果相等,则说明字符串 str 是回文串;否则,不是回文串。

筛选+逆序判断回文

class Solution {
public:
    bool isPalindrome(string s) {
        string str;
        for (char ch: s) {
            if (isalnum(ch)) {
                str+= tolower(ch);
            }
        }
        string str_rev(str.rbegin(), str.rend());
        return str== str_rev;
    }
};

第二种是利用双指针进行迭代比较判断回文。具体地,使用相向双指针 ij 进行判断,两指针初始化分别指向字符串首和字符串尾,随后比较两指针指向的字符是否一致,一致就我们就相向地移动双指针,每移动一次,都需要进行一次比较,如果字符不一致则提前退出迭代比较过程表明字符串 str 并非回文串。

筛选+双指针判断回文

class Solution {
public:
    bool isPalindrome(string s) {
        string str;
        for (char ch: s) {
            if (isalnum(ch)) {
                str+= tolower(ch);
            }
        }
        int n = str.size();
        int left = 0, right = n - 1;
        while (left < right) {
           if (str[left] != str[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为字符串 s 的长度,我们筛选出字符串 str 的时间复杂度为 O ( n ) O(n) O(n)。判断字符串 str 是否回文的时间复杂度为 str.size() / 2,字符串 str 最长与字符串 s 长度一致,因此判断回文的时间复杂度为 O ( n / 2 ) O(n / 2) O(n/2)。综合来看,筛选+判断的时间复杂度为 O ( n ) O(n) O(n)

空间复杂度: O ( n ) O(n) O(n),需要使用额外的空间来存放筛选后的字符,筛选后得到的字符串在最坏情况下,与原字符串一样长,因此,筛选+判断的空间复杂度为 O ( n ) O(n) O(n)

方法二:原地判断

我们可以直接在字符串 s 上使用双指针来判断回文。在比较字符是否相同之前需要先更新指针的指向,指针指向了数字或者字母字符时才进行字符相等性比较。

如果在比较中,遇到了字符不相等的情况,直接返回 false;如果直到两指针相遇都没有返回,则最后返回 true

实现代码

class Solution {
public:
    bool isPalindrome(string s) {
        int n = s.size();
        int left = 0, right = n - 1;
        while (left < right) {
            while (left < right && !isalnum(s[left])) {
                ++left;
            }
            while (left < right && !isalnum(s[right])) {
                --right;
            }
            if (left < right) {
                if (tolower(s[left]) != tolower(s[right])) {
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为字符串 s 的长度。

空间复杂度: O ( 1 ) O(1) O(1),仅使用了几个额外的变量。


知识回顾

回文串

回文串指的是正着读和反着读都是相同的字符串。常见的判断字符串是否回文有两种方法:

  • 逆序判断:如果某个字符串逆序后的字符串与原字符串相等,那么该字符串是回文的。
  • 双指针判断:迭代比较左、右指针指向的字符,字符相等则相向移动双指针直至两指针指向的字符不等返回 false,或者两指针相遇退出迭代比较,返回 true

回文串相关的题目:

  • 判断字符串是否回文;
  • 判断数字是否回文;
  • 判断链表是否回文。

双指针

双指针,指的是在遍历元素的过程中,不是使用单个指针进行访问,而是使用两个指针来访问以达到某种目的。双指针的题目有:

  • 两数之和;
  • 计算链表的中间节点。

字符串操作

字符串操作的本质是对字符进行操作,在进行相应操作之前可以通过以下 C++   API \texttt{C++ API} C++ API 对字符进行判断以及进一步的操作。

C++代码 说明
isalpha() 判断字符是否是字母
isdigit() 判断字符是否是数字
isalnum() 判断字符是否是字母或者是数字(十进制)
tolower() 输出字母的小写形式
toupper() 输出字母的大写形式

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。文章来源地址https://www.toymoban.com/news/detail-708734.html

到了这里,关于【面试经典150 | 双指针】验证回文串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【经典面试】87 字符串解码

    给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string] ,表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你

    2024年02月08日
    浏览(42)
  • 小白水平理解面试经典题目LeetCode 594 最大和谐字符串

    这道题属于字符串类型题目,解决的办法还是有很多的,暴力算法,二分法,双指针等等。 和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。 现在,给你一个整数数组 nums ,请你在所有可能的子序列中找到最长的和谐子序列的长度。 数组的子序列是一个

    2024年01月23日
    浏览(47)
  • 【面试经典150 | 双指针】两数之和

    本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更…… 专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删: Tag:介绍本题牵涉到的知识点、数据结构; 题目来源:

    2024年02月09日
    浏览(35)
  • 【前端面试3+1】12 toktn验证过程、面向对象特性、webpack和vite的区别、【字符串中的第一个唯一字符】

    用户登录:用户提供用户名和密码进行登录。 服务器验证:服务器接收到用户提供的用户名和密码,进行验证。 生成token:如果用户名和密码验证通过,服务器会生成一个token,通常包含一些加密的信息,如用户ID、过期时间等。 返回token:服务器将生成的token返回给客户端(

    2024年04月18日
    浏览(76)
  • 编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如“AMNMA“是回文。

    编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如\\\"AMNMA\\\"是回文。 测试输入:abcba 测试输出:是回文! 这道题要求编写一个函数来判断一个字符串是否是回文,并在主函数中调用该

    2024年02月03日
    浏览(64)
  • 字符串后面补最短长度的字符,使其整体成回文字符串(java)

    给定一个字符串str,只能在str的后面添加字符,想让str整体变成回文串,返回至少要添加几个字符 首先介绍下manacher 算法: Manacher 算法是一种线性时间复杂度的求解最长回文子串的算法。它的核心思想是利用已知回文信息,避免重复计算。 Manacher 算法的基本思想是通过预处

    2024年02月16日
    浏览(35)
  • PTA-判断回文字符串(python)

    判断回文字符串 作者 陈春晖 单位 浙江大学 回文就是字符串中心对称,从左向右读和从右向左读的内容是一样的。 输入一个字符串,判断该字符串是否为回文,只考虑数字和字母字符,字母的大小写没有区别。 输入格式: 输入一个字符串。 输出格式: 是回文,一行输出

    2024年04月12日
    浏览(57)
  • leetcode-344. 反转字符串、9. 回文数

    题目1: 解题方法 直接用reverse()即可 代码: 如果不用考虑改变原列表的话,还有一个方法: s[ : :-1] (字符串也可用此方式进行反转) 题目2:9. 回文数 给你一个整数 x ,如果 x 是一个回文整数,返回 true ;否则,返回 false 。 回文数是指正序(从左向右)和倒序(从右向左)

    2024年01月17日
    浏览(37)
  • C语言——oj刷题——回文字符串

    问题: 实现一个函数,判断一个字符串是否为回文字符串。 回文字符串是指正读和反读都相同的字符串。例如,\\\"level\\\"、\\\"radar\\\"和\\\"madam\\\"都是回文字符串。 要解决这个问题,我们可以使用两个指针分别指向字符串的首尾字符,然后逐步向中间移动,同时比较指针所指向的字符是

    2024年02月21日
    浏览(43)
  • 【leetcode刷题之路】面试经典150题(2)——双指针+滑动窗口+矩阵

    2 双指针 2.1 【双指针】验证回文串 题目地址:https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2envId=top-interview-150   详见代码。 2.2 【双指针】判断子序列 题目地址:https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2envId=top-interview-150   双指针挨个遍

    2024年02月19日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包