java - 获得最少数量的子词

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的子词最少？

例如：

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;
}

注意：
这与this问题有关。

最佳答案

更新：如果您反转内部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"));
    }

}