dp算法的种类
题目描述
已知一套试卷包含多个x-dp算法，即x类型的dp（保证x不为空且不包含d和p两个字符）。例如sosdp，adp，其拼接起来为sosdpadp，构成一套完整的试卷。
现在遍可以得到该试卷中存在若干类型的dp算法，你需要知道有多少种本质不同的dp算法，即有多少种不同x类型的算法。保证s可以被唯一分割为一个或多个形如x+dp的段。
示例
输入：adpbdpadp
输出：2
输入：sosdpadp
输出：2
题目解析
- 输入是一个字符串，例如 "adpbdpadp" 或 "sosdpadp"。
- 该字符串是由多个 "x-dp" 算法名称拼接而成，其中 "x" 是一个非空字符串，且不包含字符 'd' 和 'p'。
- 每个算法名称的形式是：x + "dp"，例如 "adp"（x="a"）、"bdp"（x="b"）、"sosdp"（x="sos"）等。
- 题目保证字符串可以被唯一分割成多个这样的段（即不会出现歧义分割）。
- 我们需要找出有多少种**本质不同的x类型的dp算法**，也就是不同的x（不重复的x）的个数。
例如：
- 输入 "adpbdpadp"：可以分割为 "adp", "bdp", "adp"。x的值分别是 "a", "b", "a"。不同的x有 "a" 和 "b"，所以输出2。
- 输入 "sosdpadp"：可以分割为 "sosdp" 和 "adp"。x的值分别是 "sos" 和 "a"。不同的x有 "sos" 和 "a"，所以输出2。
解题思路
由于字符串保证可以唯一分割，我们可以从前往后扫描，每次遇到 "dp" 时，就认为一个段结束（但注意：x中不包含'd'和'p'，所以不会出现歧义）。
实际上，每个段都是以 "dp" 结尾。因此，我们可以以 "dp" 作为分隔符来分割字符串。
例如："adpbdpadp" 分割后得到：["a", "b", "a"]（注意：去掉每个段末尾的"dp"后就是x）。
但是需要注意：x可能是任意长度（只要不包含'd'和'p'），所以我们需要找到所有出现"dp"的位置，然后从上一个段的结束到当前"dp"的前面就是x。
具体步骤：
初始化一个集合（Set）用于存储不同的x。
遍历字符串，寻找所有"dp"的出现位置。
对于每个"dp"出现的位置 i，那么从上一个段的结束位置（初始为0）到 i-1（即不包括 i和 i+1，因为"dp"是两个字符）就是x。
将x加入集合（自动去重）。
更新下一个段的开始位置为 i+2（因为"dp"占两个字符）。
最后，集合的大小就是本质不同的 x 的个数。
1.以dp作为分隔符
2.set集合存储分割得到的字符串x（不可重复）
3.通过charAt()方法用于返回指定索引处的字符。 参数：索引 （索引范围为从 0 到 length() - 1）
4.通过string的substring()方法，返回字符串的子串，参数：开始位置，结束位置
代码实现
public class demo {@Testpublic void test2() {String s = "adpbdpadp";System.out.println(solution2(s));}//1.以dp作为分隔符//2.set集合存储分割得到的字符串x（不可重复）//3.通过charAt()方法用于返回指定索引处的字符。索引范围为从 0 到 length() - 1。 参数：索引//4.通过string的substring()方法，返回字符串的子串，参数：开始位置，结束位置private int solution2(String s) {Set<String> set = new HashSet<>();int start=0;for (int i = 0; i < s.length(); i++) {if (s.charAt(i)=='d' && s.charAt(i+1)=='p'){String str = s.substring(start,i);set.add(str);start =i+2;i++;}}return set.size();}
}