50015. Words

I'm a slow walker, but I never walk backwards.

Problem Description

Given a word consisting of only lower case letters, please list all possible words that can be constructed by using exactly the letters from the given word. Your program must list all the constructed words in dictionary order. However, there are some consecutive letter rules we need to follow. For example, if the rule is "xy", then if the previous letter is 'x' then the next letter cannot be 'y'. There are up to 1000 rules.

For example, if you are given the word "egg", and no rules, then the possible words are "egg", "geg", and "gge" in dictionary order. However, if we have a rule "ge", then the only possible word will be "egg".

Subtasks

  • 10pt. There are no rules and the word is "abc".
  • 30pt. There are only a's and b's in the word, and there is only one rule.
  • 30pt. There are only a's, b's and c's in the word, and there are two rules.
  • 20pt. There are multiple rules and all letters could appear multiple times. n is no more than 30.
  • 10pt. There are multiple rules and all letters could appear multiple times.

Hint

Since you need to use all letters in the word, so you only need to remember the number of times each letter apears. That is, you can put the number of times each letter appears in an array of size 26. Then you can solve this recursively by enumerating all possible first character.

To solve the last subtask you need to stop the recursion if you found that any rules has been violated. You should be able to pass up to the second last subtask if you only check the rules after enumerate all permutations.

Sample Input 1

abc
0

Sample Output 1

abc
acb
bac
bca
cab
cba

Sample Input 2

ababb
1
ba

Sample Output 2

aabbb

Discussion