Получение всей комбинации элементов массива, которые образуют заданную строку

Question

Я застрял на этом вопрос интервью. Дано слово S и массив строк A. Как найти все возможные комбинации A elemnts, которые могут образовывать С. примера:

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

возможных комбинаций: («ч» + «о» + «tday») и («х» + "tday «).

благодарит

Answer 1

Вы можете использовать backtracking. Вот некоторый псевдо-код:

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 2

Можно перебирать все перестановки 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 3

Это моя ява решение, это реализация псевдо код «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); 
    } 
}