Array of Strings in Java

Question

I'm working on an algorithm to find all paths between two nodes in a graph. That's it, I was able to encode all paths in an Array of Strings as follows:

String []paths = new String[50];

Note: I'm using an array of strings to store the paths, but I can store them in any other data structure when necessary.

Sample of the data in my array would be something like the table below, note that the letters are my data the hyphens used for visualization only:

 -----------
| A | B | C |
 -----------
| D | E |   |
 -----------

All I need is to process the above array, and output all the combinations as:

ABC

AEC

DBC

DEC

I tried to solve this problem using the iterative approach "loops", but I failed. I think we might to do this with recursion, but I'm not sure how to do that. Also, I'm not aware if there is any data structure that deals with this problem. Something better to store the paths rather than an array of strings?

Anyway, here is what I'm working on with loops:

String []temp = new String[100];
for( r=0; r<paths.length ;r++ )
   for( c=0; c<paths[r].length() ;c++ )
      for( j=c+1; j<paths[r].length() ;j+1 )
         temp[r] += paths[j];

I'm sure you tried something, but it did not work, right? Could you please share some of your code? It will make it easier to help you solve the problem. — Sergey Kalinichenko
– Sergey Kalinichenko, Commented Dec 15, 2012 at 3:58

Joop Eggen · Accepted Answer · 2012-12-15 09:07:13Z

1

So the regular expression [AD][BE][C].

That would be a better data structure too: a 90 degree turning of the arrays. That would eliminate checking the lengths (ABC versus DE).

Nevertheless with your data structure:

int maxPathLength = 3; // TODO calculate
Set<String> results = new TreeSet<String>();
process(paths, "", 0);

public void process(String[] paths, String prefix, int i, Set<String> results) {
    if (i >= maxPathLength) {
        System.out.println(prefix);
        results.add(prefix);
        return;
    }
    for (String s : paths) {
         if (i < s.length()) {
             process(paths, prefix + s.charAt(i), i + 1, results);
         }
    }
}

edited Dec 15, 2012 at 9:07

answered Dec 15, 2012 at 4:10

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Array of Strings in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related