【2023美团后端-8】删除字符串的方案,限制不能连续删

小美定义一个字符申是“美丽串”，当且仅当该字符串包含”mei”连续子串。例如”meimei”、“xiaomeichan"都是美丽串，现在小美拿到了一个字符串，她准备删除一些字符，但不能删除两个连续字符。小美希望最终字符串变成美丽串，她想知道有多少种删除方案?

输入描述
一个仅包含小写字母的字符串，长度不超过 20。

输出描述
删除的方案数

示例1
input
meili

output
3

解释: 可以删除l,i,或者不删.共3种.

思路:

暴力搜索,
preDeleted记录前序的状态,false表示未操作,true表示删除.
having记录当前拥有了几个序列.
base case: 字符串遍历结束.
注意: 初始为[0,false,0], 遇到m直接置1,having=3随便操作,having<3,选用了其他字符,having置0.

代码题解

import java.util.*;public class test {static int len = 0;static String str = "";public static void main(String[] args) {Scanner sc = new Scanner(System.in);str = sc.nextLine();// 遍历字符串，找到连续的 "mei" 子串len = str.length();int count = dfs(0,false,0);System.out.println(count);}/*** 深搜* @param index 当前i* @param preDeleted 标前一个是否删除* @param having 拥有mei的数量 遇到m给1,1后遇到e给2..* @return 数量*/private static int dfs(int index, boolean preDeleted, int having) {if (index >= len) {if (having==3) {return 1;}return 0;}if (preDeleted) {//前序删除,所以当前直接跳过不删return calCount(index,having);} else {//删除+不删int tmp = dfs(index + 1, true, having);//删除return calCount(index,having)+tmp;}}/*** 处理状态的转换* @param index* @param having* @return*/private static int calCount(int index, int having) {if ((having==0||having==1||having==2) && str.charAt(index)=='m') {return dfs(index+1,false,1);//遇到m则having置1} else if (having==1 && str.charAt(index)=='e') {return dfs(index+1,false,2);//遇到e则having置2} else if ((having==2 && str.charAt(index)=='i')||having==3) {return dfs(index+1,false,3);//遇到e则having置2} elsereturn dfs(index+1,false,0);//选了其他则having置0}}