CODEWITHSUNDEEP
javarecursion
oddgamer
oddgamer

Reputation: 11

Any other shorter way to solve this problem through recursion

Suppose you have a string made up of only 'a' and 'b'. Write a recursive function that checks if the string was generated using the following rules: 1. The string begins with an 'a' 2. Each 'a' is followed by nothing or an 'a' or "bb" 3. Each "bb" is followed by nothing or an 'a' If all the rules are followed by the given string, return true otherwise return false.

public class temp {

    public static boolean checkAB(String input) {
        if (input.length() == 1) {
            if (input.charAt(0) == 'a')
                return true;
            else
                return false;
        }


        Boolean ans = checkAB(input.substring(0, input.length() - 1));
        if (ans == false)
            return ans;
        else {
            if (input.charAt(input.length() - 2) == 'a') {
                if (input.charAt(input.length() - 1) == 'a' || input.charAt(input.length() - 1) == 'b')
                    return true;
                else
                    return false;
            }
            if (input.charAt(input.length() - 2) == 'b') {
                if (input.charAt(input.length() - 3) == 'a') {
                    if (input.charAt(input.length() - 1) == 'b') {
                        return true;

                    } else
                        return false;
                }
                if (input.charAt(input.length() - 3) == 'b') {
                    if (input.charAt(input.length() - 1) == 'a') {
                        return true;

                    } else
                        return false;
                }


            } else
                return false;


        }
        return false;
    }
    public static void main(String args[]){
        System.out.println(checkAB("abbbabaaa"));
    }

}

Upvotes: 0

Views: 175

Answers (2)

C.B.
C.B.

Reputation: 304

I propose this pattern: "a+(bba+)*(bb)?"

public class ABB
{
    public static void main(String[] args)
    {
        for (String arg : args)
            checkAB(arg) ;
    }

    static void checkAB(String s)
    {
        System.out.printf("%s -> %b\n", s, s.matches("a+(bba+)*(bb)?")) ;
    }
}

Upvotes: 1

Alexander Terekhov
Alexander Terekhov

Reputation: 894

Something like:

 public boolean isValid(String str) {
    if (str.startsWith("a")) {
        final String substring = str.substring(1);
        return (substring.startsWith("a") || substring.startsWith("bb")) ? isValid(substring) : substring.isEmpty();

    } else if (str.startsWith("bb")) {
        final String substring = str.substring(2);
        return (substring.startsWith("a")) ? isValid(substring) : substring.isEmpty();

    } else {
        return false;
    }
}

Upvotes: 0

Related Questions