网站建设全部流程图,有特色的网站设计,用手机做app用什么软件最好,wordpress微信qq登录647. 回文子串
题目#xff1a;给你一个字符串 s #xff0c;请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串#xff0c;即使是由相同的字…647. 回文子串
题目给你一个字符串 s 请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。
思路因为这题的 字符串长度为 1 s.length 1000所以可以直接采用暴力的方法解题我们直接列举出所有的出现字符串的种类然后每一个可能出现的字符串拿去判断判断如果正确num 数值就加一。
class Solution {int num 0;public int countSubstrings(String s) {for(int i 0;is.length();i){for(int j i1;js.length();j){if(method(s.substring(i,j))){num;}}}return num;}public boolean method(String s){int left 0;int right s.length()-1;while(leftright){if(s.charAt(left)!s.charAt(right)){return false;}left;right--;}return true;}
} 思路以每个字符为中心向两边扩展判断是否为回文数需要注意的是需要分情况考虑第一种情况回文串是单数的情况第二种情况回文串是双数的情况。
class Solution {int num 0;public int countSubstrings(String s) {for(int i 0;is.length();i){int left1 i;int right1 i;int left2 i;int right2 i1;while(left10 right1s.length()){if(s.charAt(left1) s.charAt(right1)){num;left1--;right1;}else{break;}}while(left20 right2s.length()){if(s.charAt(left2) s.charAt(right2)){num;left2--;right2;}else{break;}}}return num; }
} 516.最长回文子序列
题目给你一个字符串 s 找出其中最长的回文子序列并返回该序列的长度。子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。
class Solution {public int longestPalindromeSubseq(String s) {int n s.length();int[][] dp new int[n][n];for(int i n-1;i0;i--){dp[i][i] 1;char c1 s.charAt(i);for(int j i1;jn;j){char c2 s.charAt(j);if(c1 c2){dp[i][j] dp[i1][j-1]2;}else{dp[i][j] Math.max(dp[i1][j],dp[i][j-1]);}} }return dp[0][n-1];}
}
