LeetCode 647. Palindromic Substrings

LeetCode Notes [46]

Problem

Palindromic Substrings - LeetCode

Approach 1: DFS

Intuition

Search all possible outcomes and check if the substring is palindromic or not.

class Solution {
    var count = 0
    fun countSubstrings(s: String): Int {
        count = 0
        dfs(0, s, "")
        return count
    }

    private fun dfs(index: Int, s: String, curS: String, toTerminate: Boolean = false) {
        if (index >= s.length || (toTerminate && curS.isNotEmpty())) {
            if (isPalindromic(curS)) {
                count++
            }
        } else {
            dfs(index + 1, s, curS + s[index])
            dfs(index + 1, s, curS, true)
        }
    }

    private fun isPalindromic(s: String): Boolean {
        if (s.isEmpty()) return false
        for (i in 0..s.length / 2) {
            if (s[i] != s[s.length - 1 - i])
                return false
        }
        return true
    }
}

Complexity Analysis

• Time Complexity: O(2^n)
• Space Complexity: O(n)

Approach 2: Expand digits

Intuition

Start from each index and try to extend palindrome for both odd and even length.

class Solution {
    fun countSubstrings(s: String): Int {
        var count = 0
        for (i in s.indices) {
            count += extend(s, i, i)
            count += extend(s, i, i + 1)
        }
        return count
    }

    private fun extend(s: String, l: Int, r: Int): Int {
        var count = 0
        var left = l
        var right = r
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            count++
            left--
            right++
        }
        return count
    }
}

• Time Complexity: O(n²)
• Space Complexity: O(1)