第一题
Suppose there are two rhyming schemes: AABBCC and XXYYXX, tell if these two rhyming schemes are equivalent or not.
eg: AABBCC and XXYYXX are not equivalent, As A -> X, B -> Y, but C does not have a different letter, these rhyming schemes are different.
eg: ABCABC and XYZXYZ are equivalent.
Follow up question - the harder one that I could not crack.
Q: For an n-line poem, generate all possible rhyming schemes.
eg:
For a 3-line poem, -
[AAA, AAB, ABA, ABB, ABC] - 5 ways
For a 4 line poem -
[AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAB, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD] - 15 possible ways
我的解法
import java.util.*;
public class allRhymingSchemes {
static class TreeNode{
StringBuilder word;
List<TreeNode> kids;
public TreeNode(StringBuilder word) {
this.word = word;
kids = new LinkedList<TreeNode>();
}
}
public static List<String> generateAllRhymingSchemes(int n){
List<String> result = new LinkedList<String>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
StringBuilder init = new StringBuilder();
init.append('A');
TreeNode root = new TreeNode(init);
//System.out.println(root.word.toString());
queue.add(root);
while(!queue.isEmpty()) {
TreeNode line = queue.poll();
//System.out.println("Popping " + line.word.toString());
if(line.word.length() == n) {
String answer = new String(line.word);
result.add(answer);
}
else {
//Now for this, create either from one of the chars present in the parent
//or take a completely different route, which is last char + 1 (lexicographically).
StringBuilder nextStep = line.word;
HashSet<Character> set = new HashSet<Character>();
for(int i = 0; i < nextStep.length(); i++) {
//Rhyme with a previous line if we haven't already
char ch = nextStep.charAt(i);
if(!set.contains(ch)) {
//System.out.println("Appending " + ch + " to " + nextStep.toString());
StringBuilder sb = new StringBuilder(nextStep);
sb.append(ch);
//This is our new rhyming scheme
TreeNode node = new TreeNode(sb);
//System.out.println("New rhyming scheme is " + sb.toString());
//Add as a children to our tree
line.kids.add(node);
//Add this to the queue
queue.add(node);
set.add(ch);
}
}
//After rhyming with every line rhymed before
//Our third option is to create a completely new line
StringBuilder sb = new StringBuilder(nextStep);
char newOne = (char)(nextStep.charAt(nextStep.length() - 1) + 1);
sb.append(newOne);
TreeNode node = new TreeNode(sb);
//System.out.println("Not rhyming with any line before, creating rhyming scheme " + sb.toString());
line.kids.add(node);
queue.add(node);
}
}
return result;
}
public static void main(String[] args) {
List<String> answer = generateAllRhymingSchemes(5);
System.out.println(Arrays.toString(answer.toArray()));
}
}