[AC] C# Basic Solution with small optimalization


  • 0
    B

    Basic solution O(n^2).

    Note that since C#'s ElementAt method of String class is not very fast it's necessary to use char Array for any access by index.

    When we've already found palindrome long enough to be at least twice as long as the remaining part to check we can skip it since any palindrome produced over there cannot be longer than one already found.

    Thus:

    if (size - i <= len / 2) { break; }
    

    Where i - next possible center of palindrome

    public class Solution {
        int start = 0, len = 0;
        int size;
        public string LongestPalindrome(string s) {
            size = s.Length;
            if(size < 2)
                return s;
            char[] letters = s.ToCharArray();
            for(int i = 0; i < size - 1; i++) {
                if (size - i <= len / 2) {
                    break;
                }
                checkPalindrome(letters, i, i);
                checkPalindrome(letters, i, i + 1);
            }
            return s.Substring(start, len);
        }
    
        public void checkPalindrome(char[] letters, int indx1, int indx2) {
            while(indx1 >= 0 && indx2 < size && letters[indx1] == letters[indx2]){
                indx1--;
                indx2++;
            }
            if(len < indx2 - indx1 - 1) {
                len = indx2 - indx1 - 1;
                start = indx1 + 1;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.