Solution by Dávid Horváth adapted to return the biggest smallest word:
import java.util.*;
public class SubWordsFinder
{
private Set<String> words;
public SubWordsFinder(Set<String> words)
{
this.words = words;
}
public List<String> findSubWords(String word) throws NoSolutionFoundException
{
List<String> bestSolution = new ArrayList<>();
if (word.isEmpty())
{
return bestSolution;
}
long length = word.length();
int[] pointer = new int[]{0, 0};
LinkedList<int[]> pointerStack = new LinkedList<>();
LinkedList<String> currentSolution = new LinkedList<>();
while (true)
{
boolean backtrack = false;
for (int end = pointer[1] + 1; end <= length; end++)
{
if (end == length)
{
backtrack = true;
}
pointer[1] = end;
String wordToFind = word.substring(pointer[0], end);
if (words.contains(wordToFind))
{
currentSolution.add(wordToFind);
if (backtrack)
{
if (bestSolution.isEmpty() || (currentSolution.size() <= bestSolution.size() && getSmallestSubWordLength(currentSolution) > getSmallestSubWordLength(bestSolution)))
{
bestSolution = new ArrayList<>(currentSolution);
}
currentSolution.removeLast();
} else if (!bestSolution.isEmpty() && currentSolution.size() == bestSolution.size())
{
currentSolution.removeLast();
backtrack = true;
} else
{
int[] nextPointer = new int[]{end, end};
pointerStack.add(pointer);
pointer = nextPointer;
}
break;
}
}
if (backtrack)
{
if (pointerStack.isEmpty())
{
break;
} else
{
currentSolution.removeLast();
pointer = pointerStack.removeLast();
}
}
}
if (bestSolution.isEmpty())
{
throw new NoSolutionFoundException();
} else
{
return bestSolution;
}
}
private int getSmallestSubWordLength(List<String> words)
{
int length = Integer.MAX_VALUE;
for (String word : words)
{
if (word.length() < length)
{
length = word.length();
}
}
return length;
}
public class NoSolutionFoundException extends Exception
{
private static final long serialVersionUID = 1L;
}
}
I have a String contained of regular English words in lowercase. Let's say this String is already decomposed into a List of all possible subwords:
public List<String> getSubWords(String text)
{
List<String> words = new ArrayList<>();
for (int startingIndex = 0; startingIndex < text.length() + 1; startingIndex++)
{
for (int endIndex = startingIndex + 1; endIndex < text.length() + 1; endIndex++)
{
String subString = text.substring(startingIndex, endIndex);
if (contains(subString))
{
words.add(subString);
}
}
}
Comparator<String> lengthComparator = (firstItem, secondItem) ->
{
if (firstItem.length() > secondItem.length())
{
return -1;
}
if (secondItem.length() > firstItem.length())
{
return 1;
}
return 0;
};
// Sort the list in descending String length order
Collections.sort(words, lengthComparator);
return words;
}
How do I find the least amount of subwords that form the original String?
For example:
String text = "updatescrollbar";
List<String> leastWords = getLeastSubWords(text);
System.out.println(leastWords);
Output:
[update, scroll, bar]
I'm not sure how to iterate through all possibilities since they change depending on the chosen words. A start would be something like this:
public List<String> getLeastSubWords(String text)
{
String textBackup = text;
List<String> subWords = getSubWords(text);
System.out.println(subWords);
List<List<String>> containing = new ArrayList<>();
List<String> validWords = new ArrayList<>();
for (String subWord : subWords)
{
if (text.startsWith(subWord))
{
validWords.add(subWord);
text = text.substring(subWord.length());
}
}
// Did we find a valid words distribution?
if (text.length() == 0)
{
System.out.println(validWords.size());
}
return null;
}
Note:
This is related to this question.
UPDATE: The algorithm below can be much more efficient, if you reverse the inner foreach. In this case, longer words will be checked first.
This is a typical situation for a backtracking algorithm.
Store your words in a TreeSet, and implement this algorithm:
Set start and end pointer to 0. Create a stack to store previous versions of the pointer.
Generate substrings from the start pointer, while increase end pointer, and find for a known word. If a word found, store it in an array, and add the word's length to the start pointer, push this pointer to the stack. If no known word found or the last character was reached, set the start and end pointers to the previous value popped from the stack (backtracking). Repeat 2. step.
To find the least amount of subwords, you must store previous best solution, and compare its word count with the current solution's word count.
Below is an example implementation. It contains some experiment of optimization: no recursion, backtrack on a bad branch etc. You can add more optimization (for example, tracking used start positions, or look up for possible subword start positions), but it is probably unnecessary, if the parameter is a not too long word.
public class SubWordFinder {
private TreeSet<String> words = new TreeSet<String>();
public SubWordFinder(Collection<String> words) {
this.words.addAll(words);
}
public List<String> findSubWords(String word) throws NoSolutionFoundException {
List<String> bestSolution = new ArrayList<String>();
if (word.isEmpty()) {
return bestSolution;
}
long length = word.length();
int[] pointer = new int[]{0, 0};
LinkedList<int[]> pointerStack = new LinkedList<int[]>();
LinkedList<String> currentSolution = new LinkedList<String>();
while (true) {
boolean backtrack = false;
for (int end = pointer[1] + 1; end <= length; end++) {
if (end == length) {
backtrack = true;
}
pointer[1] = end;
String wordToFind = word.substring(pointer[0], end);
if (words.contains(wordToFind)) {
currentSolution.add(wordToFind);
if (backtrack) {
if (bestSolution.isEmpty() || currentSolution.size() < bestSolution.size()) {
bestSolution = new ArrayList<String>(currentSolution);
}
currentSolution.removeLast();
} else if (!bestSolution.isEmpty() && currentSolution.size() == bestSolution.size()) {
currentSolution.removeLast();
backtrack = true;
} else {
int nextStart = end;
int[] nextPointer = new int[]{nextStart, nextStart};
pointerStack.add(pointer);
pointer = nextPointer;
}
break;
}
}
if (backtrack) {
if (pointerStack.isEmpty()) {
break;
} else {
currentSolution.removeLast();
pointer = pointerStack.removeLast();
}
}
}
if (bestSolution.isEmpty()) {
throw new NoSolutionFoundException();
} else {
return bestSolution;
}
}
public class NoSolutionFoundException extends Exception {
private static final long serialVersionUID = 1L;
}
}
Tests:
public class SubWordFinderTest {
@Test
public void generalTest() throws SubWordFinder.NoSolutionFoundException {
List<String> words = new ArrayList<String>();
words.add("ab");
words.add("abc");
words.add("cd");
words.add("cde");
words.add("de");
words.add("e");
SubWordFinder finder = new SubWordFinder(words);
assertEquals(new ArrayList<String>(), finder.findSubWords(""));
assertEquals(Arrays.asList("ab", "cde"), finder.findSubWords("abcde"));
assertEquals(Arrays.asList("cd", "cde"), finder.findSubWords("cdcde"));
assertEquals(Arrays.asList("abc", "cd"), finder.findSubWords("abccd"));
assertEquals(Arrays.asList("de", "e", "e", "e", "e"), finder.findSubWords("deeeee"));
try {
finder.findSubWords("ae");
fail();
} catch (SubWordFinder.NoSolutionFoundException e) {
}
try {
finder.findSubWords("abcccd");
fail();
} catch (SubWordFinder.NoSolutionFoundException e) {
}
try {
finder.findSubWords("abcdex");
fail();
} catch (SubWordFinder.NoSolutionFoundException e) {
}
}
@Test
public void dictionaryTest() throws IOException, SubWordFinder.NoSolutionFoundException {
String resourceDir = "/path_to_resources";
InputStream inputStream = getClass().getResource(resourceDir + "/20k.txt").openStream();
InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
List<String> words = new ArrayList<String>();
String line;
while ((line = bufferedReader.readLine()) != null) {
words.add(line);
}
SubWordFinder finder = new SubWordFinder(words);
assertEquals(Arrays.asList("bromide", "freshet"), finder.findSubWords("bromidefreshet"));
}
}