脚本宝典收集整理的这篇文章主要介绍了1216. Valid Palindrome III,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
This is the typical DP problem, the time complexity is O(n2), Where n
is the length of string s
. This is due to the fact that we try to find result for all combinations of l and r where l and r range from 0
to n:
private int[][] visited; public boolean isValidPalindrome(String s, int k) { if (s == null || s.length() == 0) return true; int n = s.length(); visited = new int[n][n]; return helper(s, 0, n - 1) <= k; } private int helper(String s, int l, int r) { if (r <= l) return 0; if (visited[l][r] > 0) return visited[l][r]; if (s.charAt(l) == s.charAt(r)) { visited[l][r] = helper(s, l + 1, r - 1); } else { visited[l][r] = 1 + Math.min(helper(s, l, r - 1), helper(s, l + 1, r)); } return visited[l][r]; }
以上是脚本宝典为你收集整理的1216. Valid Palindrome III全部内容,希望文章能够帮你解决1216. Valid Palindrome III所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。