Solution by coderGirl


  • 0
    C

    Approach #1 Dynamic Programming [Accepted]

    Algorithm

    There is a very good tutorial which can explain the logic clearly. Here is the
    link:
    https://www.youtube.com/watch?v=l3hda49XcDE

    The code below is the representation of the same:

    Java

    public class Solution {
        public boolean isMatch(String s, String p) {
            boolean dp[][]=new boolean[s.length()+1][p.length()+1];
            dp[0][0]=true;
            for(int i=0;i<p.length();i++)
            {
                if(p.charAt(i)=='*' && dp[0][i-1]==true )
                    dp[0][i+1]=true;
            }
            for(int i=0;i<s.length();i++)
            {
                for(int j=0;j<p.length();j++)
                {
                    if(p.charAt(j)==s.charAt(i) ||p.charAt(j)=='.'  )
                        dp[i+1][j+1]=dp[i][j];
                    else if(p.charAt(j)=='*')
                    {
                        dp[i+1][j+1]=dp[i+1][j-1];
                        if(p.charAt(j-1)=='.' || p.charAt(j-1)==s.charAt(i))
                            dp[i+1][j+1]=dp[i+1][j+1]||dp[i][j+1];
                    }
    
                }
            }
            return dp[s.length()][p.length()];
        }
    }
    

    Complexity Analysis

    • Time complexity :The code above takes O(mn) time where m is the length of the text and n is the length of the pattern

    • Space complexity : O(mn)


  • 0
    S

    Line 7: it should be if (p.charAt(i)=='*' && dp[0][i]==true)


  • 0
    C

    @suhasesturi I don think so. In this line we are checking if the previous value in my dp was true.
    i is the current value of the dp which will be false initially.


Log in to reply
 

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