[String] LC 680. Valid Palindrome II

  • To verify if a string is a palindrome; maximum of 1 character difference is allowed
  • We need a way to keep track of the usage of the deletion of at most one character
  • Create a flag variable, and use recursion to keep track of the value of the variable
  • Increment l+1, decrement r-1, and compare s[l] == s[r] in order to keep track of the palindrome condition; once the condition failed, check the following
  • In the cases that both recursive_helper(s, l+1, r, True) AND recursive_helper(s, l, r-1, True) returns False, the input string is not a palindrome
  • Two-pointers
  • Simple Recursion
class Solution:
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s)-1

def helper(s,l,r,flag):
while l<r:
if s[l]==s[r]:
l+=1
r-=1
else:
if flag:
return False
else:
return helper(s,l+1,r,True) or helper(s,l,r-1,True)
return True

return helper(s,l,r,False)
  • Time: The maximum depth of recursion is O(N/2) → O(N)
  • Space: O(1) since we are not creating extra objects

--

--

--

Data Engineering & Analytics

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Codidate: an Advanced Online Technical Interview Platform

Mockk: Better to way to mock in Kotlin than Mockito

Is It Too Late To Learn Programming?

Docker goes brr: deploy anywhere, anytime.

Year in Review 2018: Key Learnings and Personal Achievements

Quest 2 — Waltz of the Wizard update comparison

Safe Automatic Cleanup of Old Objects (on OpenStack Swift Containers)

Learn AlphaGo & Python (03)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Iris S

Iris S

Data Engineering & Analytics

More from Medium

Recursion — Recursive Search

Artist Upscalecracc Values Building A Solid Team

Clustering different types of NBA players using Hierarchical Agglomerative Clustering (HAC)