Recursion 102

Questions on Strings

Let's look at a question where we have to skip a character from the given string using recursion.

package Recursion.Subsequence;

public class SkipAcharacter {
    public static void main(String[] args) {
        skip("","bacccad");

        skipping("bacccad");

    }

    public static void skip(String p, String up){
        if(up.isEmpty()){
            System.out.println(p);
            return;
        }

        char ch = up.charAt(0);

        if(ch == 'a'){
            skip(p,up.substring(1));
        }else{
            skip(p + ch, up.substring(1));
        }

    }

    public static String skipping(String str){
        if(str.isEmpty()){
            return "";
        }
        char ch = str.charAt(0);

        if(ch == 'a'){
            return skipping(str.substring(1));
        }else {
            return ch + skipping(str.substring(1));
        }
    }

}

Print possible subsequences of a given sequence of strings

package Recursion.Subsequence;

public class subsets {
    public static void main(String[] args) {
        subsequence("","abc");
    }

    public static void subsequence(String p, String up){
        if(up.isEmpty()){
            System.out.println(p);
            return;
        }

        char ch = up.charAt(0);

        subsequence(p, up.substring(1));
        subsequence(p + ch, up.substring(1));
    }
}

print all possible subsequences as a list.

package Recursion.Subsequence;

import java.util.ArrayList;

public class subsets {
    public static void main(String[] args) {
        System.out.println(subsequenceRet("","abc"));
    }

    public static ArrayList<String> subsequenceRet(String p, String up){
        if(up.isEmpty()){
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }

        char ch = up.charAt(0);

        ArrayList<String> left = subsequenceRet(p + ch, up.substring(1));
        ArrayList<String> right = subsequenceRet(p,up.substring(1));

        left.addAll(right);
        return left;
    }
}

Print the Ascii value of all characters

package Recursion.Subsequence;

import java.util.ArrayList;

public class Ascii {
    public static void main(String[] args) {
        subseqAscii("","abc");
    }

    public static void subseqAscii(String p, String up){
        if(up.isEmpty()){
            System.out.println(p);
            return;
        }

        char ch = up.charAt(0);
        subseqAscii(p + ch,up.substring(1));
        subseqAscii(p,up.substring(1));
        subseqAscii(p + (ch + 0), up.substring(1));
    }
}

Return all the Ascii values as a list

package Recursion.Subsequence;

import java.util.ArrayList;

public class Ascii {
    public static void main(String[] args) {
        System.out.println(subSeqRet("","abc"));
    }

    public static ArrayList<String> subSeqRet(String p, String up){
        if(up.isEmpty()){
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }

        char ch = up.charAt(0);
        ArrayList<String> first = subSeqRet(p + ch, up.substring(1));
        ArrayList<String> second = subSeqRet(p, up.substring(1));
        ArrayList<String> last = subSeqRet(p + (ch + 0), up.substring(1));

        first.addAll(second);
        first.addAll(last);

        return first;
    }
}

Permutations

Rearrange alphabets

Print the different permutations of different ordering of each alphabet.

package Recursion.Subsequence;

public class permutationStrings {
    public static void main(String[] args) {
        permutations(" ","abc");
    }

    public static void permutations(String p, String up){
        if(up.isEmpty()){
            System.out.println(p);
            return;
        }

        char ch = up.charAt(0);

        for (int i = 0; i <= p.length(); i++) {
            String f = p.substring(0, i);
            String s = p.substring(i, p.length());
            permutations(f + ch + s, up.substring(1));
        }
    }
}

Print the alphabets in form of a list.

package Recursion.Subsequence;

import java.util.ArrayList;

public class permutationStrings {
    public static void main(String[] args) {
        System.out.println(permutationList("","abc"));
    }

    public static ArrayList<String> permutationList(String p, String up){
        if(up.isEmpty()){
            ArrayList<String> list = new ArrayList<>();
            list.add(p);
            return list;
        }

        char ch = up.charAt(0);

        ArrayList<String> ans = new ArrayList<>();

        for (int i = 0; i <= p.length(); i++) {
            String f = p.substring(0, i);
            String s = p.substring(i, p.length());
            ans.addAll(permutationList(f+ch+s,up.substring(1)));
        }
        return ans;
    }
}