How could we create an algorithm to check if a string is the result of two merged strings?

Question

I am doing the following programming exercise: Merged String Checker

1) I have tried the following code:

import java.util.*;

public class StringMerger {
  public static boolean isMerge(String s, String part1, String part2) {
    System.out.println("\n\ns: "+s);
    System.out.println("part1: "+part1);
    System.out.println("part2: "+part2);
    if(!s.isEmpty() && part1.isEmpty() && part2.isEmpty()) return false;
    if( ( part1==null || part1.isEmpty() && part2.equals(s) ) || part2==null || part2.isEmpty() && part1.equals(s) ){
      return true;
    }

    /*Check if complete words from s are in part1 or part2*/

    List<String> sList = new ArrayList(Arrays.asList(s.split(" ")));
    List<String> part1List = new ArrayList(Arrays.asList(part1.split(" ")));
    List<String> part2List = new ArrayList(Arrays.asList(part2.split(" ")));
    System.out.println("sList: "+Arrays.toString(sList.toArray()));
    System.out.println("part1List: "+Arrays.toString(part1List.toArray()));
    System.out.println("part2List: "+Arrays.toString(part2List.toArray()));

    for(Iterator<String> it = sList.iterator(); it.hasNext(); ){
      String word = it.next();
      if(word.equals(part1List.get(0))){
        it.remove();
        part1List.remove(0);
        System.out.println("sList: "+Arrays.toString(sList.toArray()));
        System.out.println("part1List: "+Arrays.toString(part1List.toArray()));
      }else if(word.equals(part2List.get(0))){
        it.remove();
        part2List.remove(0);
        System.out.println("sList: "+Arrays.toString(sList.toArray()));
        System.out.println("part2List: "+Arrays.toString(part2List.toArray()));        
      }
    }

    s=String.join(" ",sList);
    part1=String.join(" ",part1List);
    part2=String.join(" ",part2List);
    System.out.println("\n\ns: "+s);
    System.out.println("part1: "+part1);
    System.out.println("part2: "+part2);

    /*Check if s first character is part1 or part2 initial character*/

    for(char letter : s.toCharArray()){
      System.out.println("letter: "+letter);
      System.out.println("part1: "+part1);
      System.out.println("part2: "+part2);

      if(!part1.isEmpty() && letter == part1.charAt(0)){
        part1 = part1.substring(1);
        System.out.println("part1: "+part1);
        s = s.substring(1);
      }else if(!part2.isEmpty() && letter==part2.charAt(0)){
        part2 = part2.substring(1);
        System.out.println("part2: "+part2);
        s = s.substring(1);
      }
      System.out.println("s: "+s);

      System.out.println("s.substring(0,part1.length()): "+s.substring(0,part1.length()));

      if(s.substring(0,part1.length()).equals(part1)){
        s=s.substring(part1.length());
        part1="";
        System.out.println("are equal, s: "+s);
      }else if(s.substring(0,part2.length()).equals(part2)){
        s=s.substring(part2.length());
        part2="";
        System.out.println("are equal, s: "+s);
      }

      if(s.isEmpty() || (part1.length()==0 && part2.length()==0) ) break;
    }
    System.out.println("\n\ns: "+s);
    System.out.println("part1: "+part1);
    System.out.println("part2: "+part2);
    return s.isEmpty() && part1.isEmpty() && part2.isEmpty();
  }
}

And I would like you to explain: why does it fail the following test‽

import org.junit.Test;
import static org.junit.Assert.*;

public class StringMergerTest {

  @Test
  public void suffledPartsLetters(){
    assertTrue("",StringMerger.isMerge("Can we merge it? Yes, we can!","nwe me?s, e cn","Ca erg it Yewa!"));
  }

}

I have identified in the trace where is behaves unexpectedly:

letter: **r**
part1: ?s, e cn
part2: e**r**g it Yewa!
s: rge it? Yes, we can!
s.substring(0,part1.length()): rge it? 

letter: **g**
part1: ?s, e cn
part2: er**g** it Yewa!
s: rge it? Yes, we can!
s.substring(0,part1.length()): rge it? 

I understand that letter r and g are not being detected because of the code just checks if it is the first character in part1 or part2.

However I do not fully understand how could we fix the previous code to let it handle this case, could you help me please?

Besides I have also researched and found this post which describes some exercises' javascript solutions:

CodeWars/ Merged String Checker

I tried to write the recursive one without looking at the solution, and I came up with:

public class StringMerger {
  public static boolean isMerge(String s, String part1, String part2) {
    System.out.println("\n\ns: "+s);
    System.out.println("part1: "+part1);
    System.out.println("part2: "+part2);

    if(s.length()!= (part1.length()+part2.length()) ){
      System.out.println("lengths are different");
      return false;
    }
    if(s.length()==0) {
      System.out.println("s.length is 0");
      return true;
    }
    if(part1.length()>0 && s.charAt(0)==part1.charAt(0)){
      System.out.println("s first char is part1 first char");
      isMerge(s.substring(1),part1.substring(1),part2);
    }
    if(part2.length()>0 && s.charAt(0)==part2.charAt(0)){
      System.out.println("s first char is part2 first char");
      isMerge(s.substring(1),part1,part2.substring(1));
    }
    return false;
  }
}

Why does the previous one fail the following tests?

import org.junit.Test;
import static org.junit.Assert.*;

public class StringMergerTest {

  @Test
  public void normalHappyFlow() {
    assertTrue("codewars can be created from code and wars", StringMerger.isMerge("codewars", "code", "wars"));
    assertTrue("codewars can be created from cdwr and oeas", StringMerger.isMerge("codewars", "cdwr", "oeas"));
    assertFalse("Codewars are not codwars", StringMerger.isMerge("codewars", "cod", "wars"));
  }

  @Test
  public void suffledPartsLetters(){
    assertTrue("",StringMerger.isMerge("Can we merge it? Yes, we can!","nwe me?s, e cn","Ca erg it Yewa!"));
  }

}

I expected that when all letters are matched with part1 or part2 letters, and s is empty with length 0, it would output true.

However it outputs false even when it detects s.length is 0.

The trace is:

s: codewars
part1: code
part2: wars
s first char is part1 first char


s: odewars
part1: ode
part2: wars
s first char is part1 first char


s: dewars
part1: de
part2: wars
s first char is part1 first char


s: ewars
part1: e
part2: wars
s first char is part1 first char


s: wars
part1: 
part2: wars
s first char is part2 first char


s: ars
part1: 
part2: ars
s first char is part2 first char


s: rs
part1: 
part2: rs
s first char is part2 first char


s: s
part1: 
part2: s
s first char is part2 first char


s: 
part1: 
part2: 
s.length is 0

How could we also fix the previous code? And why does it fails to pass the tests?

I have also read:

Best way to convert an ArrayList to a string ConcurrentModificationException for ArrayList java : remove words from ArrayList<String> Removing items from a list Converting array to list in Java Checking if a string is empty or null in Java

Answer 1

This is tricky when part1 and part2 both have same characters at certain index. We can't guarantee which one would match later. So, this is like a binary tree where we have 2 options at each stage in case of clash.

Only way to find out is to explore both options. So you create a queue which holds an integer array of size 2. First index moves part1's pointer and second index moves part2's pointer in case of a match. If we reach a stage where both have reached their lengths completely and if current iteration character in String is also last, we return true, else we return false.

Note that there can also be instances where the current character in iteration didn't match anyone from the queue. In that case, we return false as well since we are looking for a complete match. This is taken care in the below code by the variable took.

Snippet:

import java.util.*;
public class StringMerger {
    public static boolean isMerge(String s, String part1, String part2) {  
      if(s.length() == 0){
        if(part1.length() == 0 && part2.length() == 0) return true;
        return false;
      }
      Queue<int[]> q = new LinkedList<int[]>();
      q.offer(new int[]{0,0});
      for(int i=0;i<s.length();++i){
          int size = q.size();  
          boolean took = false;
          for(int j=0;j<size;++j){
            int[] t = q.poll();            
            if(t[0] < part1.length() && s.charAt(i) == part1.charAt(t[0])){
              if(t[0] + 1 == part1.length() && t[1] == part2.length() && i == s.length() - 1) return true;
              took = true;
              q.offer(new int[]{t[0] + 1,t[1]});
            }

            if(t[1] < part2.length() && s.charAt(i) == part2.charAt(t[1])){
                if(t[1] + 1 == part2.length() && t[0] == part1.length() && i == s.length() - 1) return true;
                took = true;
                q.offer(new int[]{t[0],t[1] + 1});
            }            
          }

          if(took == false) return false;
      }

      return false;
    }
}

Answer 2

Consider case below:

S = eefe
    ^

with A = e and B = eef You can't take the first e with A, because resulting substring would then be efe and B can't match efe.

So in case of ambiguity you have to explore the two condition: should A take or should B take ?

the recursion would be:

// return true if A and B can match S, false otherwise
bool AOrB(s, iS, iA, iB) {
  if (iS > s.length) {
    // we consumed all chars in S: SUCCESS
    return true
  }

  a = A[iA]
  b = B[iB]
  s = S[iS]

  // consider all possibilities...
  if (a == s) {
    if (b == s) {
      // we need to explore both cases
      return AOrB(s, iS+1, iA+1, iB) || AOrB(s, iS+1, iA, iB+1)
    } else {
      // only A is candidate!
      return AOrB(s, iS+1, iA+1, iB)
    }
  } else {
    if (b == s) {
      // only B is candidate
      return AOrB(s, iS+1, iA, iB+1)
    } else {
      // no one matches s
      return false
    }
  }
}

This can be simplified as

AOrB(s, iS, iA, iB) {
  if (iS > s.length) {
    return true
  }

  a = A[iA]
  b = B[iB]
  s = S[iS]

  // consider all possibilities...
  bool hasSolution = false
  if (a == s) {
    hasSolution ||= AOrB(s, iS+1, iA+1, iB)
  }
  if (b == s) {
    hasSolution ||= AOrB(s, iS+1, iA, iB+1)
  }
  return hasSolution
}

which is equivalent to

AOrB(s, iS, iA, iB) {
  if (iS > s.length) {
    return true
  }

  a = A[iA]
  b = B[iB]
  s = S[iS]

  return a == s && AOrB(s, iS+1, iA+1, iB) || b == s && AOrB(s, iS+1, iA, iB+1)
}

Finally, you may take the dynamic approach route:

• You build the candidates starting from S[0] (so 0 candidates if nor A or B matches S[0], 1 if only A or B matches, or 2 candidates if both match)
• Then you use each of those candidates as starting point for s[1], and so forth

dpAOrB (S) {
  // a candidate is a couple { iA, iB } where iA is the next char to be matched by A
  // initially you only have one candidate: the couple { iA: 0, iB: 0 }
  candidates = new Set({ iA: 0, iB: 0 })
  foreach(s of S) {

    nextCandidates = new Set()
    foreach (candidate of candidates) {

      if(A[candidate.iA] == s) {
        nextCandidates.push({
          iA: iA + 1, // A can take, that's a candidate
          iB: candidate.iB
        })
      }

      if(B[candidate.iB] == s) {
        nextCandidates.push({
          iA: iA,
          iB: candidate.iB + 1
        })
      }
    }
    // if we could not generate any candidate, we can't match S
    if (nextCandidates.empty () {
      return false
    }
    candidates = nextCandidates
  }
  // we consumed all chars of S!
  return true
}

Below just some demo just to show "it works"

function dpAOrB (S, A, B) {
  let candidates = [{ iA: 0, iB: 0 }]
  return S.split('').every(s => {

    const nextCandidates = []
    candidates.forEach(({ iA, iB }) => {
      A[iA] === s && nextCandidates.push({ iA: iA + 1, iB })
      B[iB] === s && nextCandidates.push({ iA, iB: iB + 1 })
    })
    candidates = nextCandidates
    return nextCandidates.length
  })
}
console.log(dpAOrB('Can we merge it? Yes, we can!', 'nwe me?s, e cn', 'Ca erg it Yewa!'))
console.log(dpAOrB("codewars", "code", "wars"))
console.log(dpAOrB("codewars", "cdwr", "oeas"))
console.log(dpAOrB("codewars", "cod", "wars"))
console.log(dpAOrB("a ttest", "a tt", "tes")) // thx Turo

---

Improvement: no dupplication

Lastly, as exhibed by Turo's code

We can notice that we can have dupplicate candidates.

Consider S = 'aaaabc', A='aab', B='aac'. After having consumed 'aa':

  candidates [
    { iA: 2, iB: 0 },
    { iA: 1, iB: 1 },
    { iA: 1, iB: 1 },
    { iA: 0, iB: 2 }
  ]

Here we took in order AA, AB, BA, BB. However AB and BA both lead to the candidate { iA: 1, iB: 1 }

So we can shrink the space state we explore by considering the hash key iA+''+iB and avoid dupplicates.

function dpAOrB (S, A, B) {
  let candidates = new Map([[0+'_'+0, { iA: 0, iB: 0 }]])
  return S.split('').every(s => {

    const nextCandidates = new Map()
    ;[...candidates].forEach(([_, { iA, iB }]) => {
      A[iA] === s && nextCandidates.set([iA+1, iB].join('_'), { iA: iA + 1, iB })
      B[iB] === s && nextCandidates.set([iA, iB+1].join('_'), { iA, iB: iB + 1 })
    })
    candidates = nextCandidates
    // notice only one { iA: 1, iB: 1 }
    console.log('candidates', [...candidates.values()])
    return nextCandidates.size
  })
}
console.log(dpAOrB("aaaa", "aab", "aac"))

Answer 3

inspired by Olivier's answer, tests from grodzi and Turo
(does not respect order)

public class StringMerger {

    final static class MergePart {

        private String str;

        public MergePart(String str) {
            this.str = str;
        }
        private void removeCharFromStr(int index) {
            str = new StringBuilder(str).deleteCharAt(index).toString();
        }
        public boolean isComplete() {
            return str.length() == 0;
        }
        public boolean compare(char c) {
            if (isComplete()) return false;
            int index = str.indexOf(c);
            if (index < 0) return false;
            removeCharFromStr(index);
            return true;
        }
    }

    static boolean isMerge(String s, String part1, String part2) {
        MergePart m1 = new MergePart(part1);
        MergePart m2 = new MergePart(part2);
        for(char c : s.toCharArray())
        {
            if (m1.compare(c)) continue;
            if (m2.compare(c)) continue;
            return false;
        }
        return m1.isComplete() && m2.isComplete();
    }

    public static void main(String []args) {
        System.out.println(isMerge("Can we merge it? Yes, we can!", "nwe me?s, e cn", "Ca erg it Yewa!")); // true
        System.out.println(isMerge("codewars", "code", "wars")); // true
        System.out.println(isMerge("codewars", "cdwr", "oeas")); // true
        System.out.println(isMerge("codewars", "cod", "wars")); // false
        System.out.println(isMerge("a ttest", "a tt", "tes")); // true
    }
}

Answer 4

You forgot some returns at the recursive isMerge-calls, so you end up in the return false at the bottom.

if (isMerge(...)) {
     return true;
}

EDIT: forgot to check the other way if the first one fails

And, for the fun of it, here a classical(maybe historic already) approach to do this without recursion(if there could bey cycles in your states you'd need a Set<State> closed to check for it):

public class StringMerger2 {

    private class State {
        String current;
        String left;
        String right;

        public State(String current, String left, String right) {
            super();
            this.current = current;
            this.left = left;
            this.right = right;
        }

    }

    private Queue<State> open = new LinkedList<>();

    private String target;

    public StringMerger2(String target, String part1, String part2) {
        super();
        this.target = target;

        open.add(new State("", part1, part2));
    }

    public boolean isMerge() {
        while (!open.isEmpty()) {
            State state = open.poll();
            System.out.println(state.current + ":" + state.left + ":" + state.right);
            if (state.current.equals(target)) {
                return true;
            }
            int pos = state.current.length();
            if (pos == target.length()) { // for safety reasons, one should never end here
                return false;
            }
            if (state.left.startsWith(target.substring(pos, pos + 1))) {
                open.add(new State(state.current + state.left.charAt(0), state.left.substring(1), state.right));
            }
            if (state.right.startsWith(target.substring(pos, pos + 1))) {
                open.add(new State(state.current + state.right.charAt(0), state.left, state.right.substring(1)));
            }

        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(new StringMerger2("a ttest", "a tt", "tes").isMerge());
        System.out.println(
                new StringMerger2("Can we merge it? Yes, we can!", "nwe me?s, e cn", "Ca erg it Yewa!").isMerge());
        System.out.println(new StringMerger2("codewars", "code", "wars").isMerge());
        System.out.println(new StringMerger2("codewars", "cdwr", "oeas").isMerge());
        System.out.println(new StringMerger2("codewars", "cod", "wars").isMerge());
        System.out.println(new StringMerger2("a ttest", "a tt", "tes").isMerge());
        System.out.println(new StringMerger2("a ttest", " tta", "tes").isMerge());

    }
}

Answer 5

Based on @Olivier answer, and without looking at it while redoing the codewars exercise, we could also write:

public class StringMerger {
    public static boolean isMerge/*🔗🔗*/(String s, String part1, String part2) {
      System.out.println("\n\ns: "+s);
      System.out.println("part1: "+part1);
      System.out.println("part2: "+part2);
      if(s.isEmpty() && part1.isEmpty() && part2.isEmpty()) return true;
      if(part1.equals(part2)) return false;
      int pointer1 = 0, pointer2 = 0;
      for(char letter : s.toCharArray()){
        if(pointer1 < part1.length() && part1.charAt(pointer1)==letter){
          pointer1++;
        }
        if(pointer2 < part2.length() && part2.charAt(pointer2)==letter){
          pointer2++;
        }
      }
      System.out.println("pointer1: "+pointer1);
      System.out.println("pointer2: "+pointer2);
      return s.length()==pointer1+pointer2 && pointer1==part1.length() && pointer2==part2.length();
    }
}

Where we just count the letters in the original string s, which can be found either in part1 or part2, and then we check if that count is equal to the length of s.

A trace could be:

s: codewars
part1: code
part2: code


s: More progress
part1: More ess
part2: pro
pointer1: 8
pointer2: 3

Answer 6

Your code is way too complex. Here's a way to do it:

public class StringMerger
{
    static boolean isMerge(String s, String part1, String part2)
    {
        int len1 = part1.length();
        int len2 = part2.length();
        int i1 = 0;
        int i2 = 0;
        for(char c : s.toCharArray())
        {
            if(i1<len1 && c==part1.charAt(i1))
                i1++;
            else if(i2<len2 && c==part2.charAt(i2))
                i2++;
            else
                return false;
        }
        return i1==len1 && i2==len2;
     }

     public static void main(String []args)
     {
         System.out.println(isMerge("codewars", "cdw", "oears"));
     }
}

EDIT: as Turo pointed out, it works only under the assumption that part1 and part2 don't share any letters.