Leetcode showing different solutions for same test case !
Nikhit Sai
48

Hello Everyone, on problem Longest Palindromic Substring I'm got wrong subimission for a particular test case but when I run that specific test case as custom one I'm getting the expected output. Here's the code:

class Solution {
public:
    
    bool isPalindrome(int i, int j, string& s, vector<vector<bool>>& dp, vector<vector<bool>>& visited) {
        if(i > j)
            return true;
        if(s[i] != s[j])
            return false;
        
        if(visited[i][j])
            return dp[i][j];
        
        visited[i][j] = true;
        bool ans = isPalindrome(i + 1, j - 1, s, dp, visited);
        dp[i][j] = ans;
        return ans;
        
    }
    string longestPalindrome(string s) {
        if(s.size() == 0 || s.size() == 1)
            return s;
        int n = s.size(), maxlen = 0, maxi, maxj;
        vector<vector<bool>>dp(n, vector<bool>(n, false));
        vector<vector<bool>>visited(n, vector<bool>(n, false));
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(isPalindrome(i, j, s, dp, visited)) {
                   if(j - i + 1 > maxlen) {
                       maxi = i; maxj = j; maxlen = j - i  + 1;
                   }
                }
            }
        }
        
        return s.substr(maxi, maxj - maxi + 1);
        
    }
};

Here's the screenshot :
image
:

Comments (1)