TopCoder problem "DirectoryTree" used in SRM 168 (Division I Level Two)

Problem Statement


Sometimes, when listing files in a filesystem, it is desirable to view the files in a tree-like format. This can provide a visual representation of which files reside in which directories.

We first define how filenames with their full paths will be given. Each filename will consist of a leading slash ('/'), followed by a sequence of names separated by slashes. The names shall consist of one or more lower case letters. The name after the last slash identifies the file, and all the other names identify the directories and subdirectories that the file is in. For example, the path "/usr/bin/bash" is the full path name of the file "bash" in the directory "bin", which is a subdirectory of "usr". "usr" resides in the root directory "/".

Next, we define how the filenames should be displayed in the tree. For each directory that has subdirectories or files, sort all the subdirectory and file names in alphabetical order, and branch them underneath the containing directory's name. A branch is accomplished by placing a plus symbol ('+') in the column under the first letter of the containing directory's name (use preceding spaces to place the plus character in the correct column). Then place a dash character ('-') after the plus symbol. Finally, place the name of the subdirectory or file after the dash. If that name is a subdirectory which has its own elements, perform the same branching steps for that subdirectory before doing the next element of the containing directory. Finally, if two elements of a directory are not on adjacent lines in the output, connect their '+' symbols by putting vertical bars ('|') in the same column as the '+' symbols for all the lines in between the two elements. One special case, the root directory will be output as "ROOT", and will always be the first line in the output. To visually see the result of this method, look at the examples.

Given a String[] files, which contains full path file names, return a String[] with the file and directory names displayed in a tree format as defined above.



Method signature:String[] display(String[] files)
(be sure your method is public)


-files will have between 1 and 50 elements, inclusive
-Each element of files will be a sequence of words formed by one or more lower case letters, separated by single forward slash characters ('/').
-In each element of files, the first character will be a slash, and the last character will not be a slash.
-Each element of files will have between 1 and 50 characters, inclusive.
-There will be no repeated elements in files
-If you append a slash to any element of files, it will not be an exact prefix of any other element of files. In other words, full path file names cannot also be used as directory names.
-The result will not have more than 100 elements in the String[]


{"/usr/lib/libc", "/usr/bin/find", "/home/schveiguy/bashrc",
 "/usr/bin/bash", "/usr/local/bin/ssh"}
{ "ROOT",
 "| +-schveiguy",
 "|   +-bashrc",
 "  +-bin",
 "  | +-bash",
 "  | +-find",
 "  +-lib",
 "  | +-libc",
 "  +-local",
 "    +-bin",
 "      +-ssh" }
Note at each slash, how the branching occurs, and how the file and directory names are sorted. Also note how the lines do not extend when there are no more elements in a directory.
{"/dir/dir/file", "/dir/file", "/file",
 "/dir/sharedname/dir", "/dir/dir/sharedname"}
{ "ROOT",
 "| +-dir",
 "| | +-file",
 "| | +-sharedname",
 "| +-file",
 "| +-sharedname",
 "|   +-dir",
 "+-file" }
Directory names and file names can be reused, as long as they are used in different directories. Also, files can be listed alongside directories. Note the use of "sharedname" as a file and a directory.
{ "ROOT",
 "  +-a",
 "  | +-a",
 "  |   +-a",
 "  |     +-a",
 "  |     | +-a",
 "  |     |   +-a",
 "  |     +-b",
 "  |       +-a",
 "  |         +-a",
 "  +-b",
 "    +-a",
 "      +-a",
 "        +-a",
 "          +-a",
 "            +-a" }

Problem url:

Problem stats url:




lbackstrom , brett1479

Problem categories:

String Manipulation, String Parsing