Question

1312. Minimum Insertion Steps to Make a String Palindrome

中文文档

Description

Given a string s. In one step you can insert any character at any index of the string.

Return _the minimum number of steps_ to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

 

Example 1:

Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

 

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solutions

Solution 1

class Solution:
  def minInsertions(self, s: str) -> int:
    @cache
    def dfs(i: int, j: int) -> int:
      if i >= j:
        return 0
      if s[i] == s[j]:
        return dfs(i + 1, j - 1)
      return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

    return dfs(0, len(s) - 1)

class Solution {
  private Integer[][] f;
  private String s;

  public int minInsertions(String s) {
    this.s = s;
    int n = s.length();
    f = new Integer[n][n];
    return dfs(0, n - 1);
  }

  private int dfs(int i, int j) {
    if (i >= j) {
      return 0;
    }
    if (f[i][j] != null) {
      return f[i][j];
    }
    int ans = 1 << 30;
    if (s.charAt(i) == s.charAt(j)) {
      ans = dfs(i + 1, j - 1);
    } else {
      ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
    }
    return f[i][j] = ans;
  }
}

class Solution {
public:
  int minInsertions(string s) {
    int n = s.size();
    int f[n][n];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (i >= j) {
        return 0;
      }
      if (f[i][j] != -1) {
        return f[i][j];
      }
      int ans = 1 << 30;
      if (s[i] == s[j]) {
        ans = dfs(i + 1, j - 1);
      } else {
        ans = min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
      }
      return f[i][j] = ans;
    };
    return dfs(0, n - 1);
  }
};

func minInsertions(s string) int {
  n := len(s)
  f := make([][]int, n)
  for i := range f {
    f[i] = make([]int, n)
    for j := range f[i] {
      f[i][j] = -1
    }
  }
  var dfs func(i, j int) int
  dfs = func(i, j int) int {
    if i >= j {
      return 0
    }
    if f[i][j] != -1 {
      return f[i][j]
    }
    ans := 1 << 30
    if s[i] == s[j] {
      ans = dfs(i+1, j-1)
    } else {
      ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
    }
    f[i][j] = ans
    return ans
  }
  return dfs(0, n-1)
}

Solution 2

class Solution:
  def minInsertions(self, s: str) -> int:
    n = len(s)
    f = [[0] * n for _ in range(n)]
    for i in range(n - 2, -1, -1):
      for j in range(i + 1, n):
        if s[i] == s[j]:
          f[i][j] = f[i + 1][j - 1]
        else:
          f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
    return f[0][-1]

class Solution {
  public int minInsertions(String s) {
    int n = s.length();
    int[][] f = new int[n][n];
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (s.charAt(i) == s.charAt(j)) {
          f[i][j] = f[i + 1][j - 1];
        } else {
          f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
        }
      }
    }
    return f[0][n - 1];
  }
}

class Solution {
public:
  int minInsertions(string s) {
    int n = s.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (s[i] == s[j]) {
          f[i][j] = f[i + 1][j - 1];
        } else {
          f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
        }
      }
    }
    return f[0][n - 1];
  }
};

func minInsertions(s string) int {
  n := len(s)
  f := make([][]int, n)
  for i := range f {
    f[i] = make([]int, n)
  }
  for i := n - 2; i >= 0; i-- {
    for j := i + 1; j < n; j++ {
      if s[i] == s[j] {
        f[i][j] = f[i+1][j-1]
      } else {
        f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
      }
    }
  }
  return f[0][n-1]
}

Solution 3

class Solution:
  def minInsertions(self, s: str) -> int:
    n = len(s)
    f = [[0] * n for _ in range(n)]
    for k in range(2, n + 1):
      for i in range(n - k + 1):
        j = i + k - 1
        if s[i] == s[j]:
          f[i][j] = f[i + 1][j - 1]
        else:
          f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
    return f[0][n - 1]

class Solution {
  public int minInsertions(String s) {
    int n = s.length();
    int[][] f = new int[n][n];
    for (int k = 2; k <= n; ++k) {
      for (int i = 0; i + k - 1 < n; ++i) {
        int j = i + k - 1;
        if (s.charAt(i) == s.charAt(j)) {
          f[i][j] = f[i + 1][j - 1];
        } else {
          f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
        }
      }
    }
    return f[0][n - 1];
  }
}

class Solution {
public:
  int minInsertions(string s) {
    int n = s.size();
    int f[n][n];
    memset(f, 0, sizeof(f));
    for (int k = 2; k <= n; ++k) {
      for (int i = 0; i + k - 1 < n; ++i) {
        int j = i + k - 1;
        if (s[i] == s[j]) {
          f[i][j] = f[i + 1][j - 1];
        } else {
          f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
        }
      }
    }
    return f[0][n - 1];
  }
};

func minInsertions(s string) int {
  n := len(s)
  f := make([][]int, n)
  for i := range f {
    f[i] = make([]int, n)
  }
  for k := 2; k <= n; k++ {
    for i := 0; i+k-1 < n; i++ {
      j := i + k - 1
      if s[i] == s[j] {
        f[i][j] = f[i+1][j-1]
      } else {
        f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
      }
    }
  }
  return f[0][n-1]
}