Why am I getting TLE for O(n*n) solution ??


  • 0
    S
    class Solution {
        func longestPalindrome(_ s: String) -> String {
            let length = s.characters.count
            if(length == 1) {
                return s
            }
            var isSubStringPalindrome = [[Bool]](repeating:([Bool](repeating: false, count: length+1)), count: length+1)
            var longestTillNow = String(s[s.startIndex])
            for index in 0...length-1 {
                isSubStringPalindrome[index][index] = true
                isSubStringPalindrome[index][index+1] = true
            }
            for len in 2...length {
                for index in 0...length-len {
                    let startIndex = s.index(s.startIndex, offsetBy:index)
                    let endIndex = s.index(startIndex, offsetBy:len)
                    let lastIndex = s.index(startIndex, offsetBy:len-1)
                    if(isSubStringPalindrome[index+1][index+len-1] && (s[startIndex] == s[lastIndex])) 
                    {
                        isSubStringPalindrome[index][index+len] = true
                        if(longestTillNow.characters.count < len) {
                            longestTillNow = s[startIndex..<endIndex]                        
                        }
                    }
                }
            }
            return longestTillNow
        }
    }

Log in to reply
 

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