680. Valid Palindrome II

这道题的暴力解法很简单,先check如果不删除任何字符,是否字符串是回文,如果不是,再挨个删除每个字符,check删除字符之后是否是回文。

时间复杂度O(n2), n是字符串s的长度,字符串很长的情况下会TLE,算法如下:

class Solution {     public boolean validPalindrome(String s) {         if(checkPalindrom(s))             return true;         for(int i=0;i<s.length();i++){             if(checkPalindrom(s.substring(0, i)+s.substring(i+1)))                 return true;         }         return false;              }          private boolean checkPalindrom(String s){         int i=0, j=s.length()-1;         while(i<j){             if(s.charAt(i)==s.charAt(j)){                 i++;                 j--;             }             else                 return false;         }         return true;     } }

上面的算法,每删掉一个字符,就要从头到尾重新挨个字符check一遍字符串,其实这个过程可以one pass,而且这个算法可以延伸到去掉任意数量的字符.

时间复杂度O(n), 算法如下:

class Solution {     public boolean validPalindrome(String s) {         return helper(s, 0, s.length()-1, 0);     }          private boolean helper(String s, int i, int j, int sum){         if(sum>1)             return false;         while(i<j && s.charAt(i)==s.charAt(j)){             i++;             j--;         }         if(i>=j)             return true;         return helper(s, i+1, j, sum+1) || helper(s, i, j-1, sum+1);     } }

 

推荐这些文章:

125. Valid Palindrome

class Solution {
public boolean isPalindrome(String s) {
s= s.toLowerCase();
int i=0, j=s.length()-1;
while(i<j){
char a = s.charAt(i);
char b = s.charAt(j);
if(!(Character.isLetter(a)||Character.isDigit(a))){
i++;
...

1216. Valid Palindrome III

This is the typical DP problem, the time complexity is O(n2), Where n is the length of string s. This is due to the fact that we try to find result for all combinations of l and r where l and r range from 0 to n:

private int[][] visited;
...

132. 分割回文串 II

给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/palindrome-partitioning-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] ok = new boolean[n][n];
fo...

剑指 Offer II 字符串

014. 字符串中的变位词
class Solution {
Map<Character,Integer> m1 =new HashMap<>();
Map<Character,Integer> m2 =new HashMap<>();
public boolean check(char c)
{
if(m1.containsKey(c)&&m1.get(c).equals(m2.get(c)))
return true;
ret...

剑指 Offer II 回溯法

086. 分割回文子字符串
class Solution {
public:
vector<vector<string>>ans;
vector<string>path;
bool check()
{
for(string x:path)
{
for(int i=0;i<x.size();i++)
{
if(x[i]!=x[x.size()-1-i])return false;
}

}
return true;
}
void dfs(int x,...

678. Valid Parenthesis String

My solution for this problem is using two stacks, it's very easy to understand:

public boolean checkValidString(String s) {
Stack<Integer> stars = new Stack<>();
Stack<Integer> stk = new Stack<>();

for (int i = 0; i < s.length(); i++) {
...

LeetCode 0065 Valid Number

原题传送门
1. 题目描述

2. Solution 1
1、思路分析
All we need is to have a couple of flags so we can process the string in liner time:
We start with trimming.
If we see [0-9] we reset the number flags.
We can only see . if we didn't see e or .
We can only see e if we didn't see e but we did see a number. We res...

Leetcode 680 验证回文串II

  c:

#include "stdbool.h"
#include <string.h>

int num = 0;

bool palind(char *s, int left, int right)
{
if (left == right || left == right + 1)
return true;
if (s[left] == s[right])
return palind(s, left + 1, right - 1);
if (num == 1)
return false;
n...

LeetCode 1209. Remove All Adjacent Duplicates in String II

原题链接在这里:https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string-ii/
题目:
Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted s...

[简单] 387. 字符串中的第一个唯一字符

https://leetcode-cn.com/problems/first-unique-character-in-a-string/

 
 一直都写着没有灵魂的代码

class Solution {
public int firstUniqChar(String s) {
if(s.length() == 1) {
return 0;
}

int ret = -1;
Set<String> st = new HashSet<>();
...

文章标题:680. Valid Palindrome II
文章链接:https://www.dianjilingqu.com/3495.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>