문자열 GeeksForGeeks의 Palindrome 하위 문자열 계산

5331 단어 javadpalgorithms
문자열이 주어지면 작업은 그 안에 있는 모든 회문 하위 문자열을 세는 것입니다. 회문 하위 문자열의 길이는 2보다 크거나 같아야 합니다.

예시

N = 5
str = "abaab"
Output
3
Explanation:
All palindrome substring are : "aba" , "aa" , "baab"


해결책


class Solution
{
    public int CountPS(String S, int N)
    {
        int count =0;
        //we will use 2d matrix for it 
        // as in the below for loops two things are changing that we have 
        //keep in track starting index and ending index of the string 
        int dp[][] = new int[N][N];
        for(int row[]: dp) Arrays.fill(row,-1);
        for(int i =0;i<N;i++){
            for(int j =i+1;j<N;j++){
                if(isPalindrome(S,i,j,dp)==1) count++;
            }
        }
        return count;
    }
    public int isPalindrome(String s, int i ,int j,int dp[][]){
        if(i>j) return 1;
        if(dp[i][j]!=-1) return dp[i][j];

        if(s.charAt(i)!=s.charAt(j)) return 0;
        return dp[i][j] = isPalindrome(s,i+1,j-1,dp);

    }
}

좋은 웹페이지 즐겨찾기