og

双指针:回文字符串(680)

Snipaste_20200703_160643.jpg 题目描述:可以删除一个字符,判断是否能构成回文字符串。
所谓的回文字符串,是指具有左右对称特点的字符串,例如 "abcba" 就是一个回文字符串。

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

        
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
var validPalindrome = function (s) { let indexLeft = 0 let indexRight = s.length - 1 while (indexLeft <= indexRight) { if (s[indexLeft] !== s[indexRight]) { if (isSymmetric(s.slice(indexLeft, indexRight))) { return true } else { if (isSymmetric(s.slice(indexLeft + 1, indexRight + 1))) { return true } else { return false } } } else { indexLeft++ indexRight-- } } return true function isSymmetric(s1) { let Left = 0 let Right = s1.length - 1 while (Left <= Right) { if (s1[Left] === s1[Right]) { Left++ Right-- } else { return false } } return true } };

js第一次写出的解法,思路:先比较两端是否相等,删除一端一个元素后再用函数判断是否是对称的

        
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
#python3 class Solution: def validPalindrome(self, s: str) -> bool: if s==s[::-1]: return True left,right=0,len(s)-1 while left<=right: if s[left]==s[right]: left+=1 right-=1 else: a,b=s[left+1:right+1],s[left:right] print(a,b) return a==a[::-1] or b==b[::-1]

主要思路:判断是否对称就是把字符串倒过来看是否相等,采用s==s[::-1]正反向字符串对称做判定,后采用双指针来做切片删除处理

思路图

Article at   2020/07/06 11:07  Published  code  Category,viewed  205  times

Relevant tags:    算法 

Address:   https://www.kedong.me/article/24

Copyright Notice: Freely reproduced for non-commercial use