农村网站建设,深圳建设工程交易服务网中标,2019wordpress使用手册,集团公司网站建设策划方案题目
给你一个字符串 s #xff0c;如果可以将它分割成三个 非空 回文子字符串#xff0c;那么返回 true #xff0c;否则返回 false 。
当一个字符串正着读和反着读是一模一样的#xff0c;就称其为 回文字符串 。
示例 1#xff1a;
输入#xff1a;s “abcbdd” …题目
给你一个字符串 s 如果可以将它分割成三个 非空 回文子字符串那么返回 true 否则返回 false 。
当一个字符串正着读和反着读是一模一样的就称其为 回文字符串 。
示例 1
输入s “abcbdd” 输出true 解释“abcbdd” “a” “bcb” “dd”三个子字符串都是回文的。 示例 2
输入s “bcbddxy” 输出false 解释s 没办法被分割成 3 个回文子字符串。
提示 3 s.length 2000 s 只包含小写英文字母。
思路
如果枚举两个边界相当于O(N^2复杂度。此时再使用双指针判断每一部分是否是回文复杂度为ON,那么整体复杂度就是O(N的三次方)。 为此我们需要将判断是否是回文的部分降为O(1)此时我们使用动态规划定义布尔二维数组f[i][j] f[i][j]1表示从i到j的子串是回文字符串为0则表示不是。那么可以写出动态规划方程 f[i][j]
当ij时一定为true当i1j时值为s[i]s[j]当j-i1时值为s[i]s[j]f[i1][j-1] 由最后一个情况可以看出计算f[i][j]时一定要先计算出f[i1][j-1]。那么i必须要从大到小遍历j必须要从小到大遍历且从i开始遍历。
代码
class Solution {public boolean checkPartitioning(String str) {char[] s str.toCharArray();int size s.length;boolean[][] f new boolean[size][size];for(int i size-1;i0;i--){for(int j i;jsize;j){if(ij) f[i][j]true;else if(i1j) f[i][j](s[i]s[j]);else {f[i][j](s[i]s[j])(f[i1][j-1]);}}}for(int i1;isize-2;i){for(int ji;jsize-1;j){if(f[0][i-1]f[i][j-1]f[j][size-1]) return true;}}return false;}
}效率分析
74ms击败74.77%使用 Java 的用户不用再优化了。
