(双指针之对撞指针)leetcode125.验证回文串-创新互联

文章目录
  • 一、题目
    • 1、题目描述
    • 2、基础框架
    • 3、原题链接
  • 二、解题报告
    • 1、思路分析
    • 2、时间复杂度
    • 3、代码详解
  • 三、本题小知识

10年积累的成都网站设计、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有越秀免费网站建设让你可以放心的选择与我们合作。一、题目 1、题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s,如果它是 回文串 ,返回 true ;否则,返回 false 。

示例 1:
输入: s = “A man, a plan, a canal: Panama”
输出:true
解释:“amanaplanacanalpanama” 是回文串。

示例 2:
输入:s = “race a car”
输出:false
解释:“raceacar” 不是回文串。

示例 3:
输入:s = " "
输出:true
解释:在移除非字母数字字符之后,s 是一个空字符串 “” 。
由于空字符串正着反着读都一样,所以是回文串。

2、基础框架 3、原题链接 二、解题报告 1、思路分析

   ( 1 ) (1) (1)判断回文串,首先想到双指针分别从首尾开始,一个往后,一个往前同时遍历,判断字符是否相同。
   ( 2 ) (2) (2)题目中的字符串中还包含了除数字字母之外的符号,要求无视这些符号,我们可以在指针遍历到这些符号时直接跳过。
   ( 3 ) (3) (3)同时题目不考虑大小写,所以除了判断字母是否相等外,如果不相等还要判断是否是对应的大小写字母。

2、时间复杂度

最坏时间复杂度为O(n),空间复杂度为O(1)

3、代码详解

C++

class Solution {public:
    bool isPalindrome(string s) {int l = 0;
        int r = s.length()-1;
        while(lwhile(isTrue(s[l]) == 0 && l< r) {l++;
            }
            while(isTrue(s[r]) == 0 && l< r) {r--;
            }
            if (isTrue(s[l]) != isTrue(s[r])) return false;
            l++;
            r--;
        }
        return true;
    }

    int isTrue (char c) {if (c >= '0' && c<= '9'){return 1 + (c-'0');
        }
        if (c >= 'a' && c<= 'z'){return 11 + (c - 'a');
        }
        if (c >= 'A' && c<= 'Z'){return 11 + (c - 'A');
        }
        return 0;
    }
};
三、本题小知识

1.对撞指针的应用

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


名称栏目:(双指针之对撞指针)leetcode125.验证回文串-创新互联
标题来源:http://myzitong.com/article/edgjp.html