我是 Java 的新手,所以这对其他人来说可能是常识......
我正在尝试编写一种方法,该方法接受任意长度的输入字符串并返回字符串的所有可能变体的列表,其中至少删除了一个“i”。
例如,输入可以是“kikikifiki”。输出将是一个列表,其中包含删除了 0 个“i”的单词(“kikikifiki”),每个单词都删除了一个“I”(“kikikifik”、“kikikifki”等),每个单词有两个“I” s 已删除(“kikikifk”、“kikikfik”等),依此类推。输出可能有任意数量的“i”。
到目前为止,我想出了一些类似这样的东西:
String word = /*input goes here; has only a-zA-Z*/;
String hypo[] = new String[10000];
String wordOriginal = word;
String temp = word;
for (int g=0;g<(wordOriginal.replaceAll("[^i]","")).length();g++) {
while (word.contains("i")) {
for(int j=0; j<numI; j++) {
//Test the current prefix with each following 'i' removed.
temp = word.substring(0,temp.indexOf("i")+j) + temp.substring(word.indexOf("i")+j+1);
hypo[index] = prefix + temp;
for (int h=j; h>0; h--)
temp = temp.substring(0,temp.indexOf("i")) + temp.substring(temp.indexOf("i")+1);
index++;
}
word = word.substring(0,word.indexOf("i")) + word.substring(word.indexOf("i")+1);
temp = word;
numI = (word.replaceAll("[^i]","")).length();
}
word = wordOriginal;
for (int ghj=0;ghj<g;ghj++)
prefix = word.substring(0,word.indexOf("i")+1);
word = word.substring(word.indexOf("i")+1);
temp = word;
numI = (word.replaceAll("[^i]","")).length();
}
不过,它不太管用。我知道我可能应该使用一个 hypo 列表而不是一个数组,但我觉得我可以做更多的事情来让它变得优雅,而且,好吧,可操作。
有什么想法吗?
-
编辑:有人建议我将所需输出与实际输出放在一起。我还添加了下面的代码以匹配我的整个代码。
输入:
rifi
DESIRED OUTPUT:(不一定按此顺序)
rf
rif
rfi
rifi
实际输出:
rf
rfi
rif
rf
f
-
输入:
kiraiki
DESIRED OUTPUT:(不一定按此顺序)
krak
kirak
kraik
kraki
kiraik
kiraki
kraiki
kiraiki
实际输出:
krak
kraiki
kiraiki
kiraiki
kraki
kraik
krak
raki
raik
rak
kiraki
kiraik
kirak
-
完整代码:
package com;
/*public class KidishToEnglish {
public static void main(String[] args) {
//BruteForce brute = new BruteForce();
//brute.bruteForce();
}
}
*/
import java.util.Scanner;
public class KidishToEnglish
{
public static void main(String[] args)
{
Scanner keyboard = new Scanner(System.in);
while(true)
{
String word = "";
//Get the word.
System.out.print("Input:\n>> ");
while (word.equals(""))
{
word = fixword(keyboard.nextLine().toLowerCase());
if (word.equals("") || word.contains(" "))
{
System.out.print("\nPlease input one single word.\n>> ");
word = "";
}
if (!legal(word))
{
System.out.print("\nThis word contains illegal letters.\n>> ");
word = "";
}
}
//Remove unnecessary letters.
if (word.substring(word.length()-1).equals("u"))
word = word.substring(0, word.length()-1);
if (word.substring(word.length()-2).equals("es"))
word = word.substring(0, word.length()-2);
if (word.substring(word.length()-2).equals("in"))
word = word.substring(0, word.length()-2);
//Set up hypotheticals. For example, "rifi" would become an array containing "rf", "rfi", "rif", and "rifi".
int numI = (word.replaceAll("[^i]","")).length();
int index = 0;
String wordOriginal = word;
String prefix = "";
String hypo[] = new String[10000];
hypo[index] = word.replace("i","");
index++;
String temp = word;
for (int g=0;g<(wordOriginal.replaceAll("[^i]","")).length();g++)
{
while (word.contains("i"))
{
for(int j=0; j<numI; j++)
{
//Test the current prefix with each following 'i' removed.
temp = word.substring(0,temp.indexOf("i")+j) + temp.substring(word.indexOf("i")+j+1);
hypo[index] = prefix + temp;
for (int h=j; h>0; h--)
temp = temp.substring(0,temp.indexOf("i")) + temp.substring(temp.indexOf("i")+1);
index++;
}
word = word.substring(0,word.indexOf("i")) + word.substring(word.indexOf("i")+1);
temp = word;
numI = (word.replaceAll("[^i]","")).length();
}
word = wordOriginal;
for (int ghj=0;ghj<g;ghj++)
prefix = word.substring(0,word.indexOf("i")+1);
word = word.substring(word.indexOf("i")+1);
temp = word;
numI = (word.replaceAll("[^i]","")).length();
}
boolean test = true;
int testnum = 0;
while (test)
{
if(testnum >= index)
test = false;
else
System.out.println(hypo[testnum]);
testnum++;
}
}
}
public static String fixword(String word)
{
word = word.replaceAll("[^a-zA-Z ]","");
word = word.trim();
return word;
}
public static boolean legal(String word)
{
return ((word.replaceAll("[abdefhikmrsuw]","")).equals(""));
}
}
最佳答案
您几乎可以像在 binary 中从 0 到 N
(其中 N 是您要查找的字符的总出现次数)一样对待它,例如00000 到 11111
。那是 (2^N) - 1 个组合,所以蛮力搜索和替换不会很好地工作。
好吧,我们可以利用它来发挥我们的优势。首先让我们创建一个数组,其中包含我们要删除的字符的所有位置。
static List<Integer> location = new ArrayList<Integer>();
static String word = "kiraiki";
static String remove = "i";
int index = word.indexOf(remove);
while (index >= 0) {
location.add(index);
index = word.indexOf(remove, index + 1);
}
现在我们有一个 N
,即 location.size();
我们需要替换的 remove
位置。让我们遍历从 0 到 N
的所有二进制组合,并替换 location.get(i)
中相应的字符位置。
public static void binaryReplace(int value){
for (int i = 0; i < Math.pow(2, value); i++) {
StringBuilder binary = new StringBuilder(Integer.toBinaryString(i));
// Add Leading '0's
for(int j = binary.length(); j < value; j++) {
binary.insert( 0, '0' );
}
// Create a temp with the original word.
StringBuilder tmp = new StringBuilder(word);
// Look for where all the '1's (trues) are in the binary number
for (int k = -1; (k = binary.indexOf("1", k + 1)) != -1; ) {
// I'm using spaces here so has to not have indexing issues with '' chars.
tmp.setCharAt(location.get(k), ' ');
}
// Now let's just replace these spaces so we can get the print out we want.
System.out.println(tmp.toString().replaceAll("\\s", ""));
}
}
binaryReplace 函数可以得到显着改进(您可以删除一些产生相同结果的二进制组合,需要进行大量搜索,等等)但这应该可以帮助您入门。
关于java - 如何在至少删除某个字母的情况下获得字符串的所有可能性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/24580927/