java - 所有可能的字符串模式
问题描述
当我有一个包含多个“P”或“S”的字符串时,例如“PPP”、“PSP”、“PSSSPPS”、“SPSPSS”,我必须找到所有将 P 替换为“Q”或“R”的模式" 并且 S 被替换为 "T" 或 "U"。
例如输入“P”->输出[“Q”,“R”];输入“PP”->输出[“QQ”、“QR”、“RR”、“RQ”];输入“PS”=>输出[“QT”,“QU”,“RT”,“RU”];
我该如何实施这个程序?关键是P和S的数量不是固定的..
我想使用 Java 但是请给我一个算法示例..
到目前为止,
String[] getAllPatterns(String toBeChanged){
List<Integer> pPlace = new ArrayList<>();
List<Integer> sPlace = new ArrayList<>();
for (int i = 0; i < toBeChanged.length(); i++) {
char c = toBeChanged.charAt(i);
if (c == 'P') pPlace.add(i);
if (c == 'S') sPlace.add(i);
}
int numP = pPlace.size();
int numS = sPlace.size();
int numCase = (int) Math.round(Math.pow(2, numP) * Math.pow(2, numS)); // 2 is P-> Q or R; S -> T or U
String[] allcases = new String[numCase];
.................
return allcases;
}
getAllPatterns("PS"); //-> {"QT","QU","RT","RU"}
getAllPatterns("SP"); //-> {"TQ","UQ","TR","UR"}
在这种情况下,“P”只能是“Q”或“R”,但在未来,可能的字符也是变量。
“P”可以是“P1”、“P2”、“P3”、...或“Pn”
解决方案
由于每个输入字符都被 2 个字符之一替换,因此替换选择恰好适合。
因此,要遍历 N 字母输入的所有组合,您可以遍历 N 位数的所有值。
在 a 中构建所有组合List
将需要大量内存,因此使用 aint
来迭代值并将输入长度限制为 30 应该不是问题。
在这种情况下,替换字符实际上是以下两个 ASCII 字符,因此我们可以将替换字符计算为replacementChar = inputChar + 1 + bit
。
这意味着代码可能看起来像这样:
static List<String> generatePatterns(String input) {
if (! input.matches("[PS]{0,30}"))
throw new IllegalArgumentException("Invalid input: " + input);
final int end = 1 << input.length();
char[] chars = new char[input.length()];
List<String> result = new ArrayList<>(end);
for (int combo = 0; combo < end; combo++) {
for (int i = input.length() - 1, bits = combo; i >= 0; i--, bits >>>= 1)
chars[i] = (char) (input.charAt(i) + 1 + (bits & 1));
result.add(new String(chars));
}
return result;
}
测试
for (String input : new String[] {"", "P", "PP", "PS", "PPP", "PSP", "PSSSPPS", "SPSPSS"}) {
List<String> result = generatePatterns(input);
System.out.println(input + " -> " + result);
}
输出
-> []
P -> [Q, R]
PP -> [QQ, QR, RQ, RR]
PS -> [QT, QU, RT, RU]
PPP -> [QQQ, QQR, QRQ, QRR, RQQ, RQR, RRQ, RRR]
PSP -> [QTQ, QTR, QUQ, QUR, RTQ, RTR, RUQ, RUR]
PSSSPPS -> [QTTTQQT, QTTTQQU, QTTTQRT, QTTTQRU, QTTTRQT, QTTTRQU, QTTTRRT, QTTTRRU, QTTUQQT, QTTUQQU, QTTUQRT, QTTUQRU, QTTURQT, QTTURQU, QTTURRT, QTTURRU, QTUTQQT, QTUTQQU, QTUTQRT, QTUTQRU, QTUTRQT, QTUTRQU, QTUTRRT, QTUTRRU, QTUUQQT, QTUUQQU, QTUUQRT, QTUUQRU, QTUURQT, QTUURQU, QTUURRT, QTUURRU, QUTTQQT, QUTTQQU, QUTTQRT, QUTTQRU, QUTTRQT, QUTTRQU, QUTTRRT, QUTTRRU, QUTUQQT, QUTUQQU, QUTUQRT, QUTUQRU, QUTURQT, QUTURQU, QUTURRT, QUTURRU, QUUTQQT, QUUTQQU, QUUTQRT, QUUTQRU, QUUTRQT, QUUTRQU, QUUTRRT, QUUTRRU, QUUUQQT, QUUUQQU, QUUUQRT, QUUUQRU, QUUURQT, QUUURQU, QUUURRT, QUUURRU, RTTTQQT, RTTTQQU, RTTTQRT, RTTTQRU, RTTTRQT, RTTTRQU, RTTTRRT, RTTTRRU, RTTUQQT, RTTUQQU, RTTUQRT, RTTUQRU, RTTURQT, RTTURQU, RTTURRT, RTTURRU, RTUTQQT, RTUTQQU, RTUTQRT, RTUTQRU, RTUTRQT, RTUTRQU, RTUTRRT, RTUTRRU, RTUUQQT, RTUUQQU, RTUUQRT, RTUUQRU, RTUURQT, RTUURQU, RTUURRT, RTUURRU, RUTTQQT, RUTTQQU, RUTTQRT, RUTTQRU, RUTTRQT, RUTTRQU, RUTTRRT, RUTTRRU, RUTUQQT, RUTUQQU, RUTUQRT, RUTUQRU, RUTURQT, RUTURQU, RUTURRT, RUTURRU, RUUTQQT, RUUTQQU, RUUTQRT, RUUTQRU, RUUTRQT, RUUTRQU, RUUTRRT, RUUTRRU, RUUUQQT, RUUUQQU, RUUUQRT, RUUUQRU, RUUURQT, RUUURQU, RUUURRT, RUUURRU]
SPSPSS -> [TQTQTT, TQTQTU, TQTQUT, TQTQUU, TQTRTT, TQTRTU, TQTRUT, TQTRUU, TQUQTT, TQUQTU, TQUQUT, TQUQUU, TQURTT, TQURTU, TQURUT, TQURUU, TRTQTT, TRTQTU, TRTQUT, TRTQUU, TRTRTT, TRTRTU, TRTRUT, TRTRUU, TRUQTT, TRUQTU, TRUQUT, TRUQUU, TRURTT, TRURTU, TRURUT, TRURUU, UQTQTT, UQTQTU, UQTQUT, UQTQUU, UQTRTT, UQTRTU, UQTRUT, UQTRUU, UQUQTT, UQUQTU, UQUQUT, UQUQUU, UQURTT, UQURTU, UQURUT, UQURUU, URTQTT, URTQTU, URTQUT, URTQUU, URTRTT, URTRTU, URTRUT, URTRUU, URUQTT, URUQTU, URUQUT, URUQUU, URURTT, URURTU, URURUT, URURUU]
推荐阅读
- google-chrome - 连接不安全 - 在 netlify 上部署我的反应应用程序并添加自定义域之后
- arrays - Flutter - 'List 类型的值
- php - 从 url 字符串回显电子邮件
- c# - 有没有更简单的方法来格式化这个字符串?
- azure - NCron 表达式“0 0/5 19-7 * * Mon,Tue,Wed”无法解析天蓝色函数
- sharepoint - SharePoint HTTP 连接器 - 无法更改无回复电子邮件的发件人姓名
- ios - 是否可以在 AWS EC2 Mac 实例上运行 iOS 模拟器?
- amazon-web-services - AWS Lambda 未通过 VPC 端点到达 SSM 服务
- python - 从列表中检查字符串的结尾
- javascript - 在页面加载时将 Javascript 变量添加到 url 的问题