-1

当我有一个包含多个“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”

4

1 回答 1

3

由于每个输入字符都被 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]
于 2020-02-16T09:47:32.427 回答