Valid Palindrome II - Leetcode 680 - Python
Vložit
- čas přidán 8. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/valid-p...
0:00 - Read the problem
0:25 - Drawing Explanation
4:01 - Coding Explanation
leetcode 680
#meta #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
Great flow of explanation. I try to solve a problem and regardless of whether I can or not, I watch the video of the problem on your channel. Either way, it helps build up the fundamentals for me.
Yes definitely
Reversing a string is not really the optimal way to determine if it’s a palindrome. It uses extra memory and you also have to iterate over the whole string. With two pointers you only iterate half the string. Still O(n) but should be a bit faster on average! But I see you mentioned it at the end of the video anyway so great job.
a solution with pointers, trivial but still
class Solution:
def validPalindrome(self, s: str) -> bool:
def isPal(lf, rh):
while lf
Awesome !!!! I admire your commitment !!! Thank you so much ....
Absolutely no fucking way. I was doing Valid Palindrome and for whatever reason, I just could not solve it. I open CZcams to see if NeetCode has a video on it and you posted it 30 minutes ago, just my luck.
One of Facebook's favourite interview question. Was asked this twice by Facebook itself.
Another one! Thanks.
Hey, I've one request, can you share your interview experience with Google in detail? If it's possible
I still don't get it. Why isn't it O(n^2) if you're reversing the string each time you check for a palindrome? Isn't that operation linear as well?
Thank you very much
# USING THE HELPER FUNCTION
class Solution:
def helper(self,s,p1,p2) :
while p1 < p2 :
if s[p1] != s[p2]:
return False
p1 += 1
p2 -= 1
return True
def validPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
if s[l] != s[r]:
# check if elements l + 1 till r + 1 is pallindrome
# check if element l till r is pallindrome
return ( self.helper(s,l + 1, r) or
self.helper(s,l, r - 1)
)
l += 1
r -= 1
return True
Can I get guidelines to practice on ABAP in the site you mentioned ?
Is it possible to do this using LCS? If the LCS of the string and its reverse version is less than str.length-1 then it is not valid palindrome.
In skipL, keeping r+1 as higher limit and will it cause index out of bound error?
Keep going I wait for your videos.
Thanks NeetCode.
I love my solution without allocating extra memory
fun validPalindrome(string: String): Boolean {
var i = 0
var j = string.lastIndex
while (i < j && string[i] == string[j]) {
i++
j--
}
return isPalindrome(string, i + 1, j) || isPalindrome(string, i, j - 1)
}
fun isPalindrome(string: String, start: Int, end: Int): Boolean {
var i = start
var j = end
while (i < j) {
if (string[i] != string[j]) {
return false
}
i++
j--
}
return true
}
Hello neetcode,
Thank you so much for your amazing and clear videos.
I have a request, Can you please explain a problem called " Minimum steps to reduce to 1 " ?
Java
class Solution {
public boolean validPalindrome(String s) {
char ar[]= s.toCharArray();
int j=ar.length-1;
int i=0;
for(;i
Any chance of posting leetcode contest solutions? 3rd and 4th if possible 🥺
Can you create a hash map and check if the number of Keys in the map is greater than 2 return false since there is more than two unique characters that if we choose to delete any of them it would still not be a palindrom. Return true if the amount of Keys is 2 or less?
For anyone having the same doubt it would not work coz you cannot change the positions of the characters and count of characters will not give you a Idea about whether a string is a palindrome or Not..Eg: acdacc , aadccc
It's not clear from the question but this solution won't work if there are two differences in the string as it returns on the first occurrence. The questions says at most one change but it doesn't say there is only one diff max.
I tried doing this by skipping the element that's not equal (if s[l+1] == s[r]: l+=1 and vice versa) and i almost understand why that doesn't work but not quite. can someone pls explain why this strat doesn't work?
with helper function O(1) space
class Solution:
def validPalindrome(self, s: str) -> bool:
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return self.is_palindrome(s, left+1, right) or self.is_palindrome(s, left, right-1)
left += 1
right -= 1
return True
def is_palindrome(self,s, start_index, end_index):
while (start_index < end_index):
if s[start_index] != s[end_index]:
return False
start_index += 1
end_index -= 1
return True
I'm a little confused about how this solution is not runtime of O(n^2).
The outside while loop is 0(n). Then the reversal (skipL/skipR[::-1]) inside of the while loop is O(n).
Since it's nested, I'd think that would be O(n^2).
Am I missing something?
No you are travelling each character at most one time which is n steps which means it should be O(length) at worst case
Shouldn't the time complexity be O(n^2) since we are iterating over n//2 times and using string reversal (i.e. s == s[::-1]) ?
(n//2) * (n) ~= O(n^2) ?
You would only need to use the string reversal at most twice though because once you have an s[l] that does not match and s[r], you return either true or false and do not continue checking the rest of the string. Therefore its just O(n).
class Solution:
def validPalindrome(self, s: str) -> bool:
def checkValid(l,r):
while l
class Solution:
def validPalindrome(self, s: str) -> bool:
def is_valid_palindrome(l,r):
while l < r:
if s[l] != s[r]:
return False
l +=1
r -=1
return True
l_pointer = 0
r_pointer = len(s)-1
while l_pointer < r_pointer:
if s[l_pointer] == s[r_pointer]:
l_pointer +=1
r_pointer -=1
else:
if is_valid_palindrome(l_pointer+1,r_pointer):
return True
if is_valid_palindrome(l_pointer,r_pointer-1):
return True
return False
return True
def validPalindrome(self, s: str) -> bool:
l=0
r=len(s)-1
while l < r:
if s[l] == s[r]:
l+=1
r-=1
else:
return s[l:r] == s[l:r][::-1] or s[l+1:r+1] == s[l+1:r+1][::-1]
return True
2:00
Again I'm first NeetCode
Congrats🎉
lol nice streak
@@NeetCode reverse link list
Heyy
Why th is this one labeled "easy"?