获取形成给定字符串的数组元素的所有组合

Question

我卡在这个面试题上了。给定一个单词 S 和一个字符串数组 A。如何找到可以形成 S 的 A 元素的所有可能组合。示例：

S = "hotday"
A = ["o","ho","h","tday"]

可能的组合是：("h"+"o"+"tday") 和 ("ho"+"tday").

谢谢

Answer 1

您可以遍历 A 的所有排列并查看哪些适合。 Python 示例实现：

import itertools
S = "hotday"
A = ["o","ho","h","tday"]
for count in range(len(A)):
    for pieces in itertools.permutations(A, count):
        if "".join(pieces) == S:
            print pieces

结果：

('ho', 'tday')
('h', 'o', 'tday')

是的，这是 O(N!)，但这对于您提供的小 A 没问题。

Answer 2

您可以使用回溯。这是一些伪代码：

def generateSolutions(unusedWords, usedWords, string, position):
    if position == string.length():
        print(usedWords)
    else:
         for word in unusedWords:
             if word is a prefix of string[position ... s.length() - 1]:
                 generateSolutions(unusedWords - word, usedWords + word, 
                                   string, position + word.length())

generateSolution(words, an empty list, input string, 0)

这个想法非常简单：我们可以只选择一个未使用的词来匹配输入字符串其余部分的前缀，并继续递归地生成所有有效组合（我假设我们可以使用给定列表中的每个词只说一次）。该解决方案具有指数时间复杂度，但在最坏的情况下不可能做得更好。例如，如果给定的字符串是 abcdef...yz 并且单词列表是 [a, b, c, ..., z, ab, cd, ..., yz]，则此类组合的数量是 2 ^ n / 2，其中 n 是给定字符串的长度.

Answer 3

这是我的java方案，是"ILoveCoding"伪代码的实现：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;


public class PossibleCombination {


    public static void printPossibleCombinations(String[] tab, String S)
    {
        ArrayList<String> used = new ArrayList<String>();
        ArrayList<String> notused = new ArrayList<String>(Arrays.asList(tab));
        printPossibleCombinations(used, notused, S,0);
    }

    private static void printPossibleCombinations(ArrayList<String> used,
            ArrayList<String> notused, String s,int pos) {
            if (pos == s.length())
            {                   System.out.println("Possible combinaiton : ");

                for(String e : used)
                {
                    System.out.print(e + " - ");
                    System.out.println();
                }
            }
            HashSet<String> prefixes = getPossiblePrefixes(s,pos);
            for(String e : notused)
            {

                if (prefixes.contains(e))
                {
                    ArrayList<String> isused = new ArrayList<String>(used);
                    isused.add(e);
                    ArrayList<String> isnotused = new ArrayList<String>(notused);
                    isnotused.remove(e);
                    printPossibleCombinations(isused, isnotused,s, pos + e.length());
                }
            }

    }

    private static HashSet<String> getPossiblePrefixes(String s, int pos) {
        HashSet<String> prefixes = new HashSet<String>();
        for(int i = pos ; i<= s.length() ; i++)
        {
            prefixes.add(s.substring(pos,i));
        }
        return prefixes;
    }

    public static void main(String[] args) {

        String[] tab = {"o","ho","h","tday"};
        String S = "hotday";
        printPossibleCombinations(tab, S);
    }
}

获取形成给定字符串的数组元素的所有组合

Getting all combination of array elements that form a given string

algorithm

recursion