Convert file name using pattern {} to a list of file names


  • 0
    K

    in BASH system, you can use "ab{1,2}" to represent two files: "ab1", "ab2". All the choices in {} need to be comma delimited.
    Print out all the file names that match the given pattern.

    Note that you can use {} in a nested way also. Example:
    "abc{{1a,1b}, {2a,}}xyz"
    Output should be "abc1axyz", "abc1bxyz", "abc2axyz", "abcxyz"
    Another example is:
    "abc{{1a,1b}{2a,}}xyz"
    Output should be "abc1a2axyz", "abc1axyz", "abc1b2axyz", "abc1bxyz"


  • 0

    @kauai I didn't see any difference between example 1 and example 2. Could you point it out?
    Why there isn't an answer abcxyz in the second example? Also isn't better abc{{1a,1b}{2a,}xyz to be abc{{1a,1b}{2a}xyz? I removed the last comma. Thank you


  • 0
    K

    The difference between the two examples is that the first one has a comma between {1a,1b} and {2a}, whereas the second one doesn't. As noted in the question, "All the choices in {} need to be comma delimited", so if there is no comma inside {}, the {} is treated as non-special {}. That's why the two examples generate different output.

    Actually, having the last comma for {2a,} would generate twice the options - xxx2ayyy and xxxyyy assuming the string is xxx{2a,}yyy.


  • 0

    @kauai Thank you very much for your detailed explanation above. I was thinking a bit over the problem and let me define as I understand it. I will ask you to confirm whether my reasonings are right or wrong.
    Example 1 :
    "abc{{1a,1b}, {2a,}}xyz"
    Output :
    abc{1a,1b}xyz => abc1axyz, abc1bxyz
    abc{2a,""}xyz => abc2axyz, abcxyz

    Example 2 :
    abc{{1a,1b}{2a,}}xyz
    Output:
    abc{{1a,1b}{2a,""}}xyz => abc{1a}{2a}xyz, abc{1a}xyz, abc{1b}{2a}xyz, abc{1b}{""}xyz => abc1a2axyz, abc1axyz, abc1b2axyz, abc1bxyz
    Comma after a symbol provides us an additional information that empty string is a valid choice. We can accept comma as OR operator


  • 0

    Here is my rough idea:

    1. For each normal string, push them sequentially into a vector.
    2. For each part in {} between 2 normal strings, transform it to a graph, and use a hash map to link the graph with the previous normal string: the key is the the index of the string in vector.
      So abc{{1a,1b}, {2a,}}xyz can be stored as:
      vector<string> {"abc", "xyz"};
      And the hash map:
      [0, graph of c{{1a,1b}, {2a,}}],
      [1, null]
    3. To generate the graph:
      a. For character inside a {}, add them as descendant nods of previous node: {a}, {b, c, d} => a-b, a-c, a-d
      b. For {, add a dummy node with empty content, so nodes in previous level can point to this dummy node and then traverse the nodes inside {}. (Ignored the dummy node in the example in part a.)
      c. For }, depends whether it's followed by ',', if yes, all nodes in previous level point to the following node, and also append an empty node in previous level, if no, we append the following nodes as "suffix" to every nodes in previous level, so when output nodes in previous level, we should also consider those suffixes, note in this case we don't append the empty node, since according to example 2, choices with "suffix" cannot be empty...
    4. To generate all possible strings, iterate through the vector, do DFS against the graph if there are any, generating all possible parts, append each possible part and continue to the next string in vector, this is another DFS process, similar with generating all combinations of a given string.

    The idea is complex, may cost > 1h to implement by my estimation. Hope someone could come up with more elegant solutions...


  • 0

    @bwv825 I also was thinking first to generate the graph


  • 0
    K

    @elmirap Yes, your understanding of the question is correct.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.