首页 > 试题广场 >

验证回文字符串(二)

[编程题]验证回文字符串(二)

热度指数：1479 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串，请问最多删除一个的情况下，能否组成一个回文字符串。

回文字符串：正着读和反着读是一样的字符串。

数据范围：字符串长度满足 $1 \le n \le 10^5 \$ ，字符串中仅包含小写英文字母

示例1

输入

"nowwon"

输出

true

示例2

输入

"nowewon"

输出

true

示例3

输入

"noweawon"

输出

true

示例4

输入

"noowwwn"

输出

false

算法知识视频讲解

一品统合

双指针。

两个指针关于字符串中间位置对称。当指针字符不匹配，但是删除一个字符就能匹配后，有且仅有一次机会删除字符。

非回文字符串的情况是：

两个指针字符不匹配，且删除一个字符之后还是不匹配，返回false。
两个指针字符不匹配，但是删除字符的机会已经使用，返回false。

class Solution {
public:
    bool palindrome(string str) {
        bool flag_delete = false;
        for (int i = 0, j = str.length() - 1; i <= j; i++, j--) {
            if (str[i] != str[j]) {
                if (!flag_delete) {
                    if (str[i + 1] == str[j]) {
                        i++;
                        flag_delete = true;
                    } else if (str[i] == str[j - 1]) {
                        j--;
                        flag_delete = true;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
                
            }
        }

        return true;
    }
};

发表于 2023-05-13 23:18:53 回复(0)

C++

奶茶之后jfjd

bool palindrome(string str) {
int tag=0;//标记是否跳过某字符
int left=0;//双指针
int right=str.length()-1;
while (left<=right) {
if(str[left]==str[right]) {
left++;
right--;
}else{ //当出现头尾元素不一样时
if(tag==0&&str[left+1]==str[right]) {
//左边跳过当前字符
tag=1;
left+=2;
right--;
}
else if(tag==0&&str[left]==str[right-1]){
//右边跳过当前字符
tag=1;
left++;
right-=2;
}
else return false;//当左边删除一个元素或者右边删除一个元素都不满足回文，则失败
}
}
return true;
}

发表于 2023-04-23 19:37:16 回复(0)

小谷围做题家

package main
//import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return bool布尔型
*/
func palindrome( str string ) bool {
    i,j:=0,len(str)-1
    for i<j{
        if str[i]!=str[j]{
            if check(str[i+1:j+1])||check(str[i:j]){
                return true
            }
            return false
        }
        i++
        j--
    }
    return true
}

func check(str string)bool{
    i,j:=0,len(str)-1
    for i<j{
        if str[i]!=str[j]{
            return false
        }
        i++
        j--
    }
    return true
}

发表于 2023-03-09 10:14:44 回复(0)

C++

阿金要努力

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return bool布尔型
     */
    bool JudgeChar(string& s, int left, int right)
    {
        while(left<right)
        {
            if(s[left++]!=s[right--])
            {
                return false;
            }
        }
        return true;
    }
    bool palindrome(string str) 
    {
        // write code here
        int left=0, right=str.size()-1;
        while(left<right)
        {
            if(str[left]!=str[right])
            {
                return JudgeChar(str, left+1, right)||
                JudgeChar(str, left, right-1);
            }
            left++;
            right--;
        }
        return true;
    }
};

发表于 2023-02-12 20:36:27 回复(0)

JavaScript Node

几号发货

提供一个删除k个字符思路

function palindrome(str) {
    function dfs(s, i, j, k) {
        if (k < 0) return false;
        if (j - i <= 1) return true;
        while (i < j) {
            if (s[i] == s[j]) {
                i++;
                j--;
            } else {
                return (
                    dfs(s, i + 1, j, k - 1) ||
                    dfs(s, i, j - 1, k - 1) ||
                    dfs(s, i + 1, j - 1, k - 2)
                );
            }
        }
        return true;
    }
    return dfs(str,0,str.length-1,1)
}

发表于 2022-11-17 12:09:06 回复(0)

Java

coffee_*

import java.util.*;


public class Solution {

    public boolean palindrome (String str) {

        char a[] =str.toCharArray();
        for(int i=0;i<a.length;i++){
            if(a[i]!=a[a.length-1-i]&&a.length-1-i-i>=2){
                return false;
            }
        }
        return true;
    }
}

发表于 2022-10-18 21:38:27 回复(0)

Java

BlueProtocol

用一下双指针就搞定了

public class Solution {
    public boolean palindrome(String str) {
        // write code here
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != chars[chars.length - 1 - i]) {
                return false;
            }
            continue;
        }
        return true;
    }
}

发表于 2022-10-10 20:33:50 回复(0)

C++

zhengluoqi

bool palindrome(string str) {
        // write code here
        int i=0,j=str.length()-1;
        for(;str[i]==str[j]&&i<=j;i++,j--){
        }
        if(i>=j)return true;
        int i1=i+1;
        int j1=j;
        for(;str[i1]==str[j1]&&i1<=j1;i1++,j1--){
        }
        if(i1>=j1)return true;
        int i2=i;
        int j2=j-1;
        for(;str[i2]==str[j2]&&i2<=j2;i2++,j2--){
        }
        if(i2>=j2)return true;
        return false;
    }

发表于 2022-07-27 12:05:42 回复(0)

Python 3

来牛客玩玩

class Solution:
    def palindrome(self , str: str) -> bool:
        # write code here
        return str == str[::-1]

发表于 2022-07-03 16:42:35 回复(0)

Python2

菜鸡升职记

# -*- coding: utf-8 -*-

# coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/130e1a9eb88942239b66e53ec6e53f51?tpId=196&tqId=40502&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        定义check(left, right)，用于判断字符串str中以str[i]开始，str[j]的连续字符串是否为回文串
        本题允许删除一个字符，这里我们使用deleted表示是否已经删除过。
        当str[i] != str[j]时：
            若delete = True，返回False
            否则：判断check(i, j-1)&nbs***bsp;check(i+1, j)
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O()
    """

    def palindrome(self, str):
        # write code here
        def check(left, right):
            i, j = left, right

            while i < j:
                if str[i] == str[j]:
                    i += 1
                    j -= 1
                elif self.deleted:
                    return False
                else:
                    self.deleted = True
                    return check(i + 1, j)&nbs***bsp;check(i, j - 1)

            return True

        left, right, self.deleted = 0, len(str) - 1, False

        return check(left, right)


if __name__ == "__main__":
    sol = Solution()

    # s = "nowwon"

    # s = "nowewon"

    s = "noweawon"

    # s = "noowwwn"

    res = sol.palindrome(s)

    print res

发表于 2022-06-26 09:32:07 回复(0)

Java

唐喻铭

import java.util.*;

public class Solution {
    boolean flag = false;
    public boolean palindrome (String str) {
        int left = 0;
        int right = str.length()-1;
        
        while(left < right) {
            if(str.charAt(left) == str.charAt(right)) {
                left ++;
                right --;
            }else {
                if(flag) {
                    //说明已经删过一次了
                    return false;
                }
                flag = true;
                //需要判断一下，删左边好还是删右边好
                return palindrome(str.substring(left,right))||
                    palindrome(str.substring(left+1,right+1));
            }
        }
        return true;
    } 
}

发表于 2022-06-13 21:53:07 回复(0)

Python 3

danspace

class Solution:
    def palindrome(self , str: str) -> bool:
        # write code here
        count = 0
        s = str[::-1]
        for i in range(len(s)):
            if s[i] != str[i]:
                count += 1
        if count > 2: return False
        return True

发表于 2022-04-22 17:09:49 回复(0)

Python 3

牛客995249227号

class Solution:
def palindrome(self , str: str) -> bool:
# write code here
n=len(str)
count=0
left=0
right=n-1
while left<right:
if(str[left]!=str[right]):
count+=1
left+=1
right-=1
if count>=2:
return False
else:
return True

发表于 2022-04-17 22:48:09 回复(0)

C++

等一个offer！

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return bool布尔型
     */
    bool palindrome(string str) {
        if(str.empty()||str.length()==1) return true;
        bool res;
        if(isP(str)){
            return true;
        }
        for(int i=0;i<str.length();i++){
            string new_str;
            new_str=str.substr(0,i)+str.substr(i+1);
            res=isP(new_str);
            if(res==false){
                return false;
            }
        }
        return true;
    }
    bool isP(string s){
        string new_str(s.rbegin(),s.rend());
        return new_str==s;
    }
};

发表于 2022-03-18 20:38:33 回复(0)

提交观点

问题信息

贪心字符串双指针

难度：

14条回答 21收藏 3120浏览

通过挑战的用户

查看代码

牛客31742...

2022-09-15 11:27:33
commoand

2022-09-13 20:28:49
FM_NowC...

2022-09-05 08:15:06
走在修行的大街上

2022-09-03 21:36:35
牛客11870...

2022-09-01 20:59:39

验证回文字符串(二)

输入

输出

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题