Рекурсивно создавая строки из 2-мерного массива символов

Question

Мне нужно создать все возможные строки из 2d-массива, чтобы первый символ начинался с charArray[0], второй символ - от charArray[1] ... и конечный символ исходит от charArray[keyLength-1].

Пример:

вход:

char[][] charArray = 
{{'m','M','L','S','X'} 
{'e','E','o','N','Z'} 
{'o','G','F','r','Y'} 
{'D','H','I','J','w'}}; 

выход:

{meoD, meoH, meoI,..., XZYJ, XZYw} //in an Array or ArrayList 

я имел рабочий раствор, который builts дерево с каждого символа в charArray[0] в качестве корня, и он сделал построение первой строки глубины, но у JVM закончилась нехватка памяти для charArray, длина которой меньше 12. Обычно я беру итеративный подход, но длина charArray (т. длина строки ключа) определяется во время выполнения, и я хотел бы найти более полное решение, чем писать оператор switch на длину строки ключа и вручную выписывать циклы для конечного числа длин строк.

Я застрял в этой небольшой части своей программы дольше, чем я хотел бы признать, поэтому любая помощь будет принята с благодарностью!

Answer 1

Вот как это можно решить:

import java.util.ArrayList; 
import java.util.List; 

public class Arrays2D { 

public static void main(String[] args) { 
    //input keys 

    String[][] charArray = 
     {{"m","M","L","S","X"}, 
     {"e","E","o","N","Z"}, 
     {"o","G","F","r","Y"}, 
     {"D","H","I","J","w"}}; 
    //print output 
    System.out.println(findCombinations(charArray)); 

} 

private static List<String> findCombinations(String[][] charArray) { 
    List<String> prev = null; 
    for (int i = 0; i < charArray.length; i++) { 
     List<String> curr = new ArrayList<String>(); 
     for (int j = 0; j < charArray[i].length; j++) { 
      if (i + 1 < charArray.length) { 
      for (int l = 0; l < charArray[i+1].length; l++) { 
        String s = charArray[i][j] + charArray[i + 1][l]; 
        curr.add(s); 
       } 
      } 

     } 
     if (prev != null && !curr.isEmpty()) { 
      prev = join(prev, curr); 
     } 
     if (prev == null) 
      prev = curr; 

    } 

    return prev; 
} 

public static List<String> join(List<String> p, List<String> q) { 
    List<String> join = new ArrayList<String>(); 
    for (String st1 : p) { 
     for (String st2 : q) { 

      if (st1.substring(st1.length() - 1).equals(st2.substring(0, 1))) { 
       String s = st1 + st2; 
       s = s.replaceFirst(st1.substring(st1.length() - 1), ""); 
       join.add(s); 
      } 

     } 
    } 

    return join; 
} 
} 

Я проверил и это правильно генерации комбинаций. Вы можете запускать и видеть вывод.