leetcode

commit 571b1ba5f8283bf4480117cdd95ee0d67705d4ed
parent e397b22b7466bdf988847742f089f7e943e78785
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sat, 22 Apr 2023 14:53:54 -0500

Completed valid palindrome ii problem using dart and recursion

Diffstat:
A
valid-palindrome/valid-palindromeV2.dart
 | 
42
++++++++++++++++++++++++++++++++++++++++++

1 file changed, 42 insertions(+), 0 deletions(-)
diff --git a/valid-palindrome/valid-palindromeV2.dart b/valid-palindrome/valid-palindromeV2.dart
@@ -0,0 +1,42 @@
+//This is the better solution to the valid palindrome ii problem.
+//The time complexity of this is O(n) where n is the length of the string.
+//Time: 311ms Beats: 51.25%
+//Memory: 154.1MB Beats: 14.29%
+
+
+class Solution {
+  bool validPalindrome(String s) {
+      if(s.length <= 2){
+          return true;
+      }
+
+
+      return is_valid(s);
+}
+int removed_vals = 0;
+
+bool is_valid(String s){
+    for(int i = 0 ; i < s.length / 2 + 1 ; ++i){
+        if(s[i] == s[s.length - i - 1]){
+            continue;
+        }
+        else{
+            if(removed_vals > 0){
+                return false;
+            }
+            removed_vals += 1;
+            bool boo2 = is_valid(s.substring(0 , i) + s.substring(i+1));
+            bool boo1 = is_valid(s.substring(0,s.length-i-1) + s.substring(s.length-i));
+            
+            if(boo1 == true){
+                return true;
+            }
+            if(boo2 == true){
+                return true;
+            }
+            return false;
+        }
+    }
+    return true;
+    }
+}