# Solution by coderGirl

• #### 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)

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

• @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.

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