leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

valid-palindromeV2.dart (1022B)

      1 //This is the better solution to the valid palindrome ii problem.
      2 //The time complexity of this is O(n) where n is the length of the string.
      3 //Time: 311ms Beats: 51.25%
      4 //Memory: 154.1MB Beats: 14.29%
      5 
      6 
      7 class Solution {
      8   bool validPalindrome(String s) {
      9       if(s.length <= 2){
     10           return true;
     11       }
     12 
     13 
     14       return is_valid(s);
     15 }
     16 int removed_vals = 0;
     17 
     18 bool is_valid(String s){
     19     for(int i = 0 ; i < s.length / 2 + 1 ; ++i){
     20         if(s[i] == s[s.length - i - 1]){
     21             continue;
     22         }
     23         else{
     24             if(removed_vals > 0){
     25                 return false;
     26             }
     27             removed_vals += 1;
     28             bool boo2 = is_valid(s.substring(0 , i) + s.substring(i+1));
     29             bool boo1 = is_valid(s.substring(0,s.length-i-1) + s.substring(s.length-i));
     30             
     31             if(boo1 == true){
     32                 return true;
     33             }
     34             if(boo2 == true){
     35                 return true;
     36             }
     37             return false;
     38         }
     39     }
     40     return true;
     41     }
     42 }