通过删除字母匹配字典最长单词
通过删除字母匹配字典最长单词
通过两个字符串最长公共子序列超时 O(mnk)
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
Collections.sort(dictionary,(a,b)->a.length()==b.length()? a.compareTo(b):b.length()-a.length());
String res="";
for(int i=0;i<dictionary.size();i++){
String s1=dictionary.get(i);
int len=getCom(s,s1);
if(len==s1.length()){
return s1;
}
}
return res;
}
public int getCom(String s1,String s2){
int n=s1.length();int m=s2.length();
int[][] dp=new int[n+1][m+1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n][m];
}
}
方式二
通过双指针判断一个字符串是否是另一个字符串子序列O(k*(m+n))
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
Collections.sort(dictionary,(a,b)->a.length()==b.length()? a.compareTo(b):b.length()-a.length());
String res="";
for(int i=0;i<dictionary.size();i++){
String s1=dictionary.get(i);
int left=0;int right=0;
while(left<s.length()&&right<s1.length()){
if (s.charAt(left) == s1.charAt(right)) {
right++;
}
left++;
}
if(right==s1.length()){
return s1;
}
}
return res;
}
}
方法三:dp预处理
定义dp[i][j]:表示从i下标字符开始,字符后面出现的位置
if((s.charAt(i)-'a')==j){
dp[i][j]=i;
}else{
dp[i][j]=dp[i+1][j];
}
i需要倒序遍历递推
class Solution {
public String findLongestWord(String s, List<String> dictionary) {
//定义dp[i][j]:表示从i位置往后,j字符出现位置
int n=s.length();
int[][] dp=new int[n+1][26];
//不存在字符位置为n
Arrays.fill(dp[n],n);
for(int i=n-1;i>=0;i--){
for(int j=0;j<26;j++){
if((s.charAt(i)-'a')==(j)){
dp[i][j]=i;
}else{
dp[i][j]=dp[i+1][j];
}
}
}
String res="";
for(int i=0;i<dictionary.size();i++){
String s1=dictionary.get(i);
boolean flag=true;
int start=0;
for(int j=0;j<s1.length();j++){
if(dp[start][s1.charAt(j)-'a']==n){
flag=false;
break;
}
start=dp[start][s1.charAt(j)-'a']+1;
}
if(flag){
if (s1.length() > res.length() || (s1.length() == res.length() && s1.compareTo(res) < 0)) {
res=s1;
}
}
}
return res;
}
}
统计只差一个字符的子串数目
统计只差一个字符的子串数目
方式一:枚举所有的子字符串,进行判断是否只有一个字符不同
方式二:通过dp[i][j]表示s字符串前i个字符和t字符串前j个字符,可以得到的最多的只差一个字符的子串数目
dp[i][j]=dp[i-1][j-1];如果对应的s[i]==t[j]
如果对应的s[i]!=t[j] dp[i][j]=g[i][j]; g[i][j]表示对应的以s前i个字符和t前j个字符,最长后缀
class Solution {
public int countSubstrings(String s, String t) {
int n=s.length();int m=t.length();
int[][] dp=new int[n][m];
for(int i=0;i<n;i++){
if(s.charAt(i)!=t.charAt(0)){
dp[i][0]=1;
}
}
for(int j=0;j<m;j++){
if(s.charAt(0)!=t.charAt(j)){
dp[0][j]=1;
}
}
int[][] g=new int[n][m];
for(int i=0;i<n;i++){
if(s.charAt(i)==t.charAt(0)){
g[i][0]=1;
}
}
for(int j=0;j<m;j++){
if(s.charAt(0)==t.charAt(j)){
g[0][j]=1;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(s.charAt(i)==t.charAt(j)){
g[i][j]=g[i-1][j-1]+1;
}else{
g[i][j]=0;
}
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(s.charAt(i)==t.charAt(j)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=g[i-1][j-1]+1;//表示分别以i,j结尾的字符串s,t的最长公共后缀
}
}
}
int res=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
res+=dp[i][j];
}
}
return res;
}
}
最长回文子序列
class Solution {
public int longestPalindromeSubseq(String s) {
int n=s.length();
int[][] dp=new int[n][n];
for(int i=0;i<n;i++){
dp[i][i]=1;
}
for(int i=n-1;i>=0;i--){
for(int j=i+1;j<n;j++){
if(s.charAt(i)==s.charAt(j)){
dp[i][j]=dp[i+1][j-1]+2;
}else{
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
}
【dp[i][j]】编辑距离
【dp[i][j]】两个字符串的删除操作
class Solution {
public int minDistance(String word1, String word2) {
int n=word1.length();int m=word2.length();
int[][] dp=new int[n+1][m+1];
for(int i=0;i<=n;i++){
dp[i][0]=i;
}
for(int j=0;j<=m;j++){
dp[0][j]=j;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
}
}
}
return dp[n][m];
}
}
【dp[i][j]】两个字符串的最小ascii删除和
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int n=s1.length();int m=s2.length();
int[][] dp=new int[n+1][m+1];
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+s1.charAt(i);
}
int[] subfix=new int[m+1];
for(int j=0;j<m;j++){
subfix[j+1]=subfix[j]+s2.charAt(j);
}
for(int i=1;i<=n;i++){
dp[i][0]=prefix[i];
}
for(int j=1;j<=m;j++){
dp[0][j]=subfix[j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=Math.min(dp[i-1][j]+s1.charAt(i-1),dp[i][j-1]+s2.charAt(j-1));
}
}
}
return dp[n][m];
}
}
所有的子字符串中的元音的个数
class Solution {
public long countVowels(String word) {
Set<Character> set=new HashSet<Character>(){
{
add('a');add('e');add('i');add('o');add('u');
}
};
int n=word.length();
long[] dp=new long[n+1];
for(int i=1;i<=n;i++){
if(set.contains(word.charAt(i-1))){
dp[i]=dp[i-1]+i;
}else{
dp[i]=dp[i-1];
}
}
long res=0;
for(int i=1;i<=n;i++){
res+=dp[i];
}
return res;
}
}
字符串的好分隔数
class Solution {
public int numSplits(String s) {
//通过前缀进行统计
Set<Character> set=new HashSet<Character>();
int n=s.length();
int[] left=new int[n];
set.add(s.charAt(0));
left[0]=1;
for(int i=1;i<s.length();i++){
if(set.contains(s.charAt(i))){
left[i]=left[i-1];
}else{
left[i]=left[i-1]+1;
}
set.add(s.charAt(i));
}
set.clear();
set.add(s.charAt(n-1));
int[] right=new int[n];
right[n-1]=1;
for(int i=n-2;i>=0;i--){
if(set.contains(s.charAt(i))){
right[i]=right[i+1];
}else{
right[i]=right[i+1]+1;
}
set.add(s.charAt(i));
}
int res=0;
for(int i=0;i<s.length()-1;i++){
if(left[i]==right[i+1]){
res++;
}
}
return res;
}
}