CODEWITHSUNDEEP
javastringrecursion
Rnam
Rnam

Reputation: 65

How to fix a recursive string check

On the first input line there will be the secret message (the sequence of digits). e.g. 1122

On the second input line there will be the cipher used for encoding the message in the given format: “{LetterX}{CodeForX}{LetterY}{CodeForY}…” where every LetterX from the original message will be encoded with CodeForX in the secret code. e.g. A1B12C11D2

Print the number of all possible original messages that can be encoded to the given secret code. On the next lines, print these messages. e.g. 3 -> AADD ABD CDD

My idea is to check the message for any letter code (e.g. "1", "12" etc.) present at the beginning of the string, and if such is found cut it out from it and proceed recursively till the end of the string is reached.

public class Main {
static List<String> gList = new ArrayList<>();

public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String message = in.readLine();     // "1122"
    String codeStr = in.readLine();     // "A1B12C11D2"
// SPLITTING LETTERS FROM CODES:
    String [] secretCode = codeStr.split("[^A-Z0-9]+|(?<=[A-Z])(?=[0-9])|(?<=[0-9])(?=[A-Z])");
    int n = secretCode.length / 2;
    String [] letters = new String [n];  // [A  B   C   D]
    String [] codes = new String [n];    // [1  12  11  2]
    for (int i = 0; i < 2 * n; i+=2) {
        letters[i/2] = secretCode[i];
        codes[i/2] = secretCode[i+1];
    }
    CodesCheck(message, letters, codes);
    System.out.println(Arrays.toString(gList.toArray()));
}
static void CodesCheck (String message, String[] letters, String[] codes) {
    for (int i = 0; i < codes.length; i++) {
        if (codes[i].length() <= message.length() && 
            codes[i].equals(message.substring(0, codes[i].length()))) {
            gList.add(letters[i]);
            String newMessage = message.substring(codes[i].length());
            if (newMessage.equals("")) {
                gList.add("|");
                return;
            }
            CodesCheck(newMessage, letters, codes);
        }
    }
}
}

When running the code above I get: [A, A, D, D, |, B, D, |, C, D, D, |] -> so in the second message the "A" letter is missing. When I debug I can see that the recursive function somehow proceeds with "122" and not "1122".

Upvotes: 2

Views: 202

Answers (2)

Max Vollmer
Max Vollmer

Reputation: 8598

That's because your recursion works like this:

 * CodesCheck with "1122" and i=0 adds A, then calls itself with "122"
 ** CodesCheck with "122" and i=0 adds A, then calls itself with "22"
 *** CodesCheck with "22" and i=3 adds D, then calls itself with "2"
 **** CodesCheck with "2" and i=3 adds D, then adds | and returns because next message is ""
 *** CodesCheck with "22" returns because i > 3
 ** CodesCheck with "122" continues with i=1, adds B, then calls itself with "2"
 *** CodesCheck with "2" and i=3 adds D, then adds | and returns because next message is ""
 ** CodesCheck with "122" continues with i=2, finds nothing, continues with i=3, finds nothing, returns because i>3
 * CodesCheck with "1122" and i=1 finds nothing, continues with i=2, adds C, calls itself with "22"
 ** CodesCheck with "22" and i=3 adds D, then calls itself with "2"
 *** CodesCheck with "2" and i=3 adds D, then adds | and returns because next message is ""
 ** CodesCheck with "22" returns because i > 3
 * CodesCheck with "1122" continues with i=3, finds nothing, then returns because i > 3

To fix this, you need to keep track of the recursive calls somehow, meaning when the method working on "122" continues with i=1 and B, you need to know that there was an A before and that you need to add that to your list before the B.

One way to do this is to use a stack:

void CodesCheck (String message, String[] letters, String[] codes, Stack<String> stack) {

When you call your method, just provide it with an empty stack:

CodesCheck(message, letters, codes, new Stack<String>());

Then instead of adding letters directly to gList, you add them to the stack and make sure you pop the local letter after leaving the current recursive or iterative branch:

stack.add(letters[i]);
final String newMessage = message.substring(codes[i].length());
if (newMessage.equals("")) {
    gList.addAll(stack);
    gList.add("|");
    stack.pop();
    return;
}
CodesCheck(newMessage, letters, codes, stack);
stack.pop();

Upvotes: 1

kutschkem
kutschkem

Reputation: 8163

The problem is not the function, it is the output:

With A you have multiple possibilities, your program prints:

A [ output of recursive call with second letter A | ] [ output of recursive call with second letter B |].

What you should be doing instead is let each call return the resulting gLists (multiple), and the calling function prepend their current letter. Only in the end should you put | in between.

Upvotes: 0

Related Questions