Given a string, I want to find all variants without transposition, only deletion. For example, given the string:
helloo
The list of variants would be as follows (separated by white space).
helloo hello heloo helo
My solution so far is to move through each character, and then if the current character matches the next character, recursively try the original and the deleted character version, as follows.
// takes String with at most two consecutive characters of any character,
// and returns an Iterable of all possible variants (e.g. hheello -> heello, hhello, ...)
private static Iterable<String> findAllVariants(String word) {
StringBuilder variant = new StringBuilder(word);
Queue<String> q = new LinkedList<String>();
findAllVariants(word, variant, 0, q);
return q;
}
// helper method
private static void findAllVariants(String word, StringBuilder variant, int currIndex, Queue<String> q) {
if (currIndex == variant.length() - 1) q.add(variant.toString());
for (int i = currIndex; i < variant.length() - 1; i++) {
char thisChar = variant.charAt(i);
char nextChar = variant.charAt(i+1);
if (thisChar == nextChar) {
// get all variants with repeat character
findAllVariants(word, variant, i+1, q);
// get all variants without repeat character;
variant = variant.deleteCharAt(i);
findAllVariants(word, variant, i, q);
}
}
}
However, I end up getting a large number of copies of answers, and none of others. When I do my algorithm on paper, it seems correct. What am I doing wrong?
Something along the lines of the following code will enable you to get all possibilities (remember to add word
itself if needed). The idea is to retreive all possibilities for removing one char (e.g. hello
results in ello hllo helo hell
). These results can in turn be used to get the possibilities for removing two chars (remove one char again). Resulting in llo elo ell
for ello
and so on...
List<String> getPossibilities(String word) {
int removeChars = word.length() - 1;
List<String> possibilities = new ArrayList();
List<String> options = Arrays.asList(word);
for(int i = 0; i <= removeChars; i++) {
List<String> results = new ArrayList();
for(String option : options) {
for(String result : removeOneChar(option)) {
if(!results.contains(result)) {
results.add(result);
}
}
}
possibilities.addAll(results);
options = results;
}
return possibilities;
}
private static List<String> removeOneChar(String word) {
List<String> results = new ArrayList();
for(int i = 0; i < word.length(); i++) {
int secondPart = i + 2;
if(secondPart <= word.length()) {
results.add(
word.substring(0, i)
+ word.substring(i + 1, word.length()));
}
else {
results.add(
word.substring(0, i));
}
}
return results;
}
Notice the if(!contains(result))
in order to prevent any duplicates.
Note I've used substring()
to accomplish this, you're approach with removeCharAt()
is a another good option. You could run some tests to see which performs better to decide which one to use. Notice using the latter could possibly remove the need of the if
in the private
method.