Searching for a String in an Array of Objects

Question

I have a Object that contains an ArrayList of self referntial objects. Each Object in that ArrayList contains the same structre upto n degrees. Now i have to search for a string in the structure and if found i have to print all the way up to the root. Here is a sample

MyClass {
string name;
ArrayList<MyClass> subClasses;
}

What data structure would be best to do this. Or do i not need one to use it.

Kind Regards

The classes themselves are the structure: they are a tree (unless subclasses can reference their ancestors in ehich case they are a directed graph). You need a tree traversing algorithm — Eli Algranti
– Eli Algranti, Commented Apr 13, 2013 at 6:37

Dev Blanked · Accepted Answer · 2013-04-13 06:40:34Z

2

You could have a method on MyClass like below

public List<String> findPathOfName(String nameToFind) {
    List<String> result = new ArrayList<String>();

    if (nameToFind.equals(name)) {
      result.add(name);
    } else {
      for (MyClass aSubClass: subClasses) {
        List<String> subResult = aSubClass.findPathOfName(nameToFind);
        if (!subResult.isEmpty()) {
           result.add(name);
           result.addAll(subResult);
           break;
        }
      }
    }

    return result;
}

basically recursively go through the structure and find the path. Returned list would contain the path like personA/personB/etc..

answered Apr 13, 2013 at 6:40

Dev Blanked

8,9153 gold badges28 silver badges33 bronze badges

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

1 Comment

rliu Over a year ago

I didn't read the code closely but this idea should work. It's worth noting to OP that this is a "depth first search" with the modification that it keeps track of the path to the desired node.

Evgeniy Dorofeev · Accepted Answer · 2013-04-13 06:58:29Z

This is http://en.wikipedia.org/wiki/Composite_pattern. Try my version

static class MyClass {
    String name;
    List<MyClass> subClasses;

    MyClass(String name) {
        this.name = name;
    }

    String search(String s, String path) {
        if (!path.isEmpty()) {
            path += "->";
        }
        path += name;
        if (!s.equals(name)) {
            if (subClasses == null) {
                return null;
            }
            for (MyClass c : subClasses) {
                return c.search(s, path);
            }
        }
        return path;
    }
}

public static void main(String[] args) throws Exception {
    MyClass c1 = new MyClass("c1");
    MyClass c2 = new MyClass("c2");
    MyClass c3 = new MyClass("c3");
    c1.subClasses = Arrays.asList(c2);
    c2.subClasses = Arrays.asList(c3);
    System.out.println(c1.search("c3", ""));
}

output

c1->c2->c3

Collectives™ on Stack Overflow

Searching for a String in an Array of Objects

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related