CODEWITHSUNDEEP
javastringrecursiondynamic-programming
thealchemist
thealchemist

Reputation: 441

Using some specific append operations on a string check whether it can be converted to other

Given two strings - an initial string, and a target string. Your code must then determine if the initial string can be converted somehow to the target string, by appending either P or Q to it (repeatedly).

However, to append P or Q, you must follow these two rules: Append P to the end Reverse the string and append Q to the end

Examples -

Examples:

Initial: PQQ, Target: PQQP,

Output: true

Initial: PQQ Target: QQPQPPPP

Output: true

Initial: P Target: PQPQQQ

Output: false

I tried to tackle this via simple recursion but not able to find it working for all of the above test cases . I don't know whether I am headed in correct direction . I welcome all the suggestions , please suggest me on this .Following is my approach 

public class Convert {

     boolean isMatch(String s1 , String s2){
        if(s1.equals(s2))
            return true;
        String  s3 = s1.concat("P");
        StringBuilder input1 = new StringBuilder();
        input1.append(s1);
        String  s4 = input1.reverse().toString();
        s4 = s4.concat("Q");    
        return isMatch(s3, s2) || isMatch(s4,s2);   
    }

    public static void main(String[] args) {

        String s1 = "PQQ";
        String s2 = "PQQP";
        Convert c1 = new Convert();
        boolean res = c1.isMatch(s1, s2);
        System.out.println(res);
    }
}

Upvotes: 0

Views: 309

Answers (1)

Stefan
Stefan

Reputation: 2395

You are very close. All you need is an exit criteria:

if (s1.length() > s2.length())
    return false;

Put it right below 

if(s1.equals(s2))
        return true;

If s1 is longer than s2 (the target string), stop looking for solutions since there is no way s1 will become s2 by adding more stuff (it is already too long).

With no exit criteria, you will loop forever. Eg "Aha, String PPPPP was not equal to String PP, lets see if Strings PPPPPP or PPPPPQ are", etc, etc, ...

Upvotes: 3

Related Questions