Получение наименьшего количества подслов
Решение по Dávid Horváth адаптирован, чтобы вернуть самое маленькое слово:
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;
}
}
у меня есть String содержит обычные английские слова в нижнем регистре. Скажем так String уже разложен в List из всех возможных подслов:
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;
}
Как найти наименьшее количество подслов, которые составляют исходную строку?
Например:
String text = "updatescrollbar";
List<String> leastWords = getLeastSubWords(text);
System.out.println(leastWords);
Выход:
[update, scroll, bar]
Я не уверен, как перебрать все возможности, так как они меняются в зависимости от выбранных слов. Начало будет примерно таким:
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;
}
Замечания:
Это связано с этим вопросом.
2 ответа
ОБНОВЛЕНИЕ: Алгоритм ниже может быть намного более эффективным, если вы измените внутренний foreach. В этом случае более длинные слова будут проверены первыми.
Это типичная ситуация для алгоритма возврата.
Храните свои слова в TreeSetи реализовать этот алгоритм:
Установите начальный и конечный указатель на
0, Создайте стек для хранения предыдущих версий указателя.Создайте подстроки из начального указателя, увеличив при этом конечный указатель, и найдите для известного слова. Если слово найдено, сохраните его в массиве и добавьте длину слова в начальный указатель, поместите этот указатель в стек. Если не найдено ни одного известного слова или был достигнут последний символ, установите начальный и конечный указатели на предыдущее значение, извлеченное из стека (возврат). Повторите 2. шаг.
Чтобы найти наименьшее количество подслов, вы должны сохранить предыдущее лучшее решение и сравнить его количество слов с количеством слов текущего решения.
Ниже приведен пример реализации. Он содержит некоторый эксперимент по оптимизации: отсутствие рекурсии, возврат на неверную ветку и т. Д. Вы можете добавить дополнительную оптимизацию (например, отслеживание использованных начальных позиций или поиск возможных начальных позиций подслов), но это, вероятно, не нужно, если параметр это не слишком длинное слово.
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;
}
}
тесты:
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"));
}
}
Это требует много возможностей сценария.
Ваш пример (updatescrollbar) имеет уже up date ate update scroll bar и все еще довольно легко, но что делать, если у вас есть слово с подсловами, которые оставляют вас с одним символом в конце строки.
Таким образом, чтобы пройти через это, вам придется многократно повторять свой список подслов, отслеживать текущую самую короткую действительную версию, соответствующую вашему тексту, и продолжать итерацию, пока не попробуете все варианты.
Вы можете уменьшить количество вариантов, например, используя алгоритм, который учитывает оставшееся пространство для сопоставления:
- Сортируйте ваши подслова по длине и попробуйте сначала поместить в текст самые длинные слова: возможное подслово длины = текст -/- сопоставленный текст. При этом будет использоваться содержимое, поэтому сопоставляемый текст по-прежнему может быть до и после уже сопоставленных слов: используйте массив для текста, чтобы было легче отслеживать сопоставляемый текст.