# DP - String

**Step1**, Defined a suitable table for DP problem

Similar to other DP problems, we are used to have a table for storing the temp solutions.

For example `2 strings comparation` problems&#x20;

ex.  #583 Delete Operation for Two Strings,  #72 Edit Distance

2D table is suitable for those cases.&#x20;

```java
int[][] dp = new int[s1.length+1][s2.length+1];
//the dp[i][j] means the answer for s1[:i](s1.substring(0,i)), s2[:j]
```

**Step 2**, List the basic base and fill the table in, it usually happen in the edge of table

Take #583 as example:&#x20;

* i = 0, j = 0 :    dp\[i]\[j] shall be 0, means both s1 and s2 are empty
* i = 0 , j != 0 : dp\[0]\[j] shall be j&#x20;
* i !=0, j =0 :  dp\[i]\[0] shall be i

```java
        for(int i = 0; i <= s1.length; i++){
            dp[i][0] = i;
        }
        
        for(int j = 0; j <= s2.length; j++){
            dp[0][j] = j;
        }
```

**Step 3**, fill in the other cells of the table by considering 2 possibiliies

* s1\[i] == s2\[j]&#x20;
* s1\[i] != s2\[j]&#x20;

```java
for( int i = 1; i <= m; i++){
	for( int j = 1; j <= n; j++){
		if(s1[i - 1] == s2[j - 1]){
			/* Your code */
		}
		else{
			/* Your code */
		}
	}
}
```

The answer is `dp[s1.length][s2.length]`

#### If you are given only one string, the template will be modified as below:

The basic concept for this template is to enumerate all substring cases

```java
int[][] dp = new int[][];
//or
boolean[][] dp = new boolean[][];

for(int dist = 1; dist < n; dist++){
    for(int i = 0; i + dist < n; i++){
        int j = dist + i;
        if(s[i] == s[j]){
            //...
        }
        else{
        
        }
    } 
}
```
