vamsu
8/4/2018 - 9:21 PM

Interleavings of two strings

Interleavings of two strings

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Solution solution =new Solution();
    String[] a = {
          null,
          "",
          "ABC",
          "A"
        };
    String[] b = {
          null,
          "",
          "ACB",
          "B"
        };
    for(int i=0;i< a.length;i++) {
      System.out.println("Input: " + a[i] + ", " + b[i] +
                       ", Result: " + solution.interleavings(a[i], b[i]));
    }
  }
  
  public Set<String> interleavings(String a, String b){
    Set<String> result = new HashSet<String>();
    if(a == null || b == null) {
      return result;
    }
    interleavingsRecur("",a,b,result);
    return result;
    
  }
   
  public void interleavingsRecur(String temp, String a, 
                              String b, Set<String> result){
    if(a.length() == 0 && b.length() == 0) {
      result.add(temp);
    }
    if(a.length() >0) {
      interleavingsRecur(temp + a.substring(0,1), a.substring(1), b, result);
    }
    if(b.length() > 0) {
      interleavingsRecur(temp + b.substring(0,1), a, b.substring(1), result);
    }    
  }  
  
}