没有域名的网站,做装修行业营销型网站,网站的建设意见,做平台的网站有哪些小美定义一个字符申是“美丽串”#xff0c;当且仅当该字符串包含”mei”连续子串。例如”meimei”、“xiaomeichan都是美丽串#xff0c;现在小美拿到了一个字符串#xff0c;她准备删除一些字符#xff0c;但不能删除两个连续字符。小美希望最终字符串变成美丽串当且仅当该字符串包含”mei”连续子串。例如”meimei”、“xiaomeichan都是美丽串现在小美拿到了一个字符串她准备删除一些字符但不能删除两个连续字符。小美希望最终字符串变成美丽串她想知道有多少种删除方案?
输入描述 一个仅包含小写字母的字符串长度不超过 20。
输出描述 删除的方案数
示例1 input meili
output 3
解释: 可以删除l,i,或者不删.共3种.
思路:
暴力搜索, preDeleted记录前序的状态,false表示未操作,true表示删除. having记录当前拥有了几个序列. base case: 字符串遍历结束. 注意: 初始为[0,false,0], 遇到m直接置1,having3随便操作,having3,选用了其他字符,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 (having3) {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 ((having0||having1||having2) str.charAt(index)m) {return dfs(index1,false,1);//遇到m则having置1} else if (having1 str.charAt(index)e) {return dfs(index1,false,2);//遇到e则having置2} else if ((having2 str.charAt(index)i)||having3) {return dfs(index1,false,3);//遇到e则having置2} elsereturn dfs(index1,false,0);//选了其他则having置0}}
