Minimum Insertion Steps to Make a String Palindrome LeetCode solution in Java

1
class Solution {
2
  public int minInsertions(String s) {
3
    StringBuilder sb = new StringBuilder(s);
4
    String str = sb.reverse().toString();
5
    int m = s.length();
6
    int n = str.length();
7
    System.out.println(str);
8
    return LCS(s, str, m, n);
9
  }
10

11
  public int LCS(String x, String y, int m, int n) {
12
    int[][] t = new int[m + 1][n + 1];
13
    for (int i = 0; i < m + 1; i++) {
14
      for (int j = 0; j < n + 1; j++) {
15
        if (m == 0 || n == 0) {
16
          t[m][n] = 0;
17
        }
18
      }
19
    }
20
    for (int i = 1; i < m + 1; i++) {
21
      for (int j = 1; j < n + 1; j++) {
22
        if (x.charAt(i - 1) == y.charAt(j - 1)) {
23
          t[i][j] = 1 + t[i - 1][j - 1];
24
        } else {
25
          t[i][j] = Math.max(t[i][j - 1], t[i - 1][j]);
26
        }
27
      }
28
    }
29
    return y.length() - t[m][n];
30
  }
31
}