how to store the char array into string array and sort that string array in java?

Question

Given 2 strings A and B, print all the interleavings of the 2 strings. An interleaved string of given two strings preserves the order of characters in individual strings and uses all the characters of both the strings. For simplicity, you can assume that the strings have unique characters.

input:
2
nkb gl
bn zh
i wrote some code but im not getting the sorted strings.

public class Test {

static void interleavings(String A, String B, char[] ans, int m, int n, int idx) 
{
    if(m==0 && n==0) 
    {
        System.out.println(ans);
        return;
    } 
    if(m != 0) 
    {
        ans[idx]=A.charAt(0);
        interleavings(A.substring(1,m), B, ans, m-1, n, idx+1);
    } 
    if(n != 0) 
    {
        ans[idx]= B.charAt(0);
        interleavings(A, B.substring(1,n), ans, m, n-1, idx+1);
    }
}
public static void main(String[] args) 
{
    Scanner s =  new Scanner(System.in);
    int t = s.nextInt();
    for(int i = 0; i < t; i++)
    {
        String s1=s.next();
        String s2=s.next();
        char [] ans = new char[s1.length()+s2.length()];
        System.out.println("Case #"+(i+1)+":");
        interleavings(s1,s2,ans,s1.length(),s2.length(),0);  
    }
}

}

My output
Case #1:
nkbgl
nkgbl
nkglb
ngkbl
ngklb
nglkb
gnkbl
gnklb
gnlkb
glnkb
Case #2:
bnzh
bznh
bzhn
zbnh
zbhn
zhbn
Expected output
Case #1:
glnkb
gnkbl
gnklb
gnlkb
ngkbl
ngklb
nglkb
nkbgl
nkgbl
nkglb
Case #2:
bnzh
bzhn
bznh
zbhn
zbnh
zhbn

I'm new to java can someone please guide me. how to over come this problem please.

Pavel Polivka · Accepted Answer · 2020-08-17 07:52:32Z

2

I would no use char array as it will make things more complicated. I would pass a current value as string. See curr + A.charAt(0) this will append the char to a String, this way you are not dealing with char.

Store results in Collection. Than you can sort the whole collection an print it when done, instead of doing it on the fly.

class Main {

    public static void interleavings(String curr, String A, String B, Set<String> result) {
        if (A.length() == 0 && B.length() == 0) {
            result.add(curr);
            return;
        }
        if (A.length() > 0) {
            interleavings(curr + A.charAt(0), A.substring(1), B, result);
        }
        if (B.length() > 0) {
            interleavings(curr + B.charAt(0), A, B.substring(1), result);
        }
    }

    public static void main(String[] args) {
        String A = "bn";
        String B = "zh";

        Set<String> result = new HashSet<>();
        interleavings("", A, B, result);

        // this will print all the results sorted
        result.stream()
              .sorted()
              .forEach(System.out::println);
    }
}

answered Aug 17, 2020 at 7:52

Pavel Polivka

8784 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Lino Over a year ago

Sidenote: The .length() == 0 checks could be replaced with .isEmpty() also the .stream().sorted() could be removed when using a TreeSet from the beginning

score 2 · Accepted Answer · 2020-08-18 20:45:54Z

2

You should swap a and b when a.compareTo(b) > 0 and then make recursive calls.

static void interleavings(String a, String b, String result) {
    if (a.isEmpty() && b.isEmpty())
        System.out.println(result);
    else if (a.compareTo(b) > 0)
        interleavings(b, a, result);
    else {
        if (!a.isEmpty())
            interleavings(a.substring(1), b, result + a.charAt(0));
        if (!b.isEmpty())
            interleavings(a, b.substring(1), result + b.charAt(0));
    }
}

and

interleavings("nkb", "gl", "");
interleavings("bn", "zh", "");

output

glnkb
gnkbl
gnklb
gnlkb
ngkbl
ngklb
nglkb
nkbgl
nkgbl
nkglb
bnzh
bzhn
bznh
zbhn
zbnh
zhbn

edited Aug 18, 2020 at 20:45

answered Aug 17, 2020 at 9:13

user4910279

2 Comments

Eklavya Over a year ago

I like the idea of swaping (no need to sort later)

sukesh Over a year ago

what will be the complexity?

Collectives™ on Stack Overflow

how to store the char array into string array and sort that string array in java?

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related