java - 我们如何创建一个算法来检查一个字符串是否是两个字符串合并的结果？

Question

我正在做以下编程练习:Merged String Checker

1)我尝试过以下代码:

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();
  }
}

我想让你解释一下:为什么它无法通过以下测试‽

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!"));
  }

}

我在跟踪中发现了行为异常的地方:

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? 

我知道字母 r 和 g 没有被检测到，因为代码只是检查它是否是第 1 部分或第 2 部分中的第一个字符。

但是我不完全明白我们如何修复之前的代码以使其处理这种情况，您能帮我吗？

此外，我还研究并发现了这篇文章，其中描述了一些练习的 javascript 解决方案:

CodeWars/ Merged String Checker

我尝试在不查看解决方案的情况下编写递归程序，然后我想出了:

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;
  }
}

为什么前一个未通过以下测试？

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!"));
  }

}

我期望当所有字母都与part1或part2字母匹配，并且s为空且长度为0时，它会输出true。

但是，即使检测到 s.length 为 0，它也会输出 false。

跟踪是:

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

我们如何修复之前的代码？为什么它无法通过测试？

我还读过:

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

考虑下面的情况:

S = eefe
    ^

其中 A = e 和 B = eef 您不能将第一个 e 与 A 一起使用，因为生成的子字符串将是 efe 且 B 无法匹配 efe。

因此，如果出现歧义，您必须探索两个条件:应该A采取还是应该B采取？

递归将是:

// 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
    }
  }
}

这可以简化为

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
}

相当于

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)
}

最后，您可以采取动态进场路线:

• 从 S[0] 开始构建候选项(如果 A 或 B 都不匹配 S[0]，则有 0 个候选项；如果只有 A 或 B 匹配，则有 1 个候选项；如果两者都匹配，则有 2 个候选项)
• 然后使用每个候选者作为 s[1] 的起点，依此类推

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
}

下面只是一些演示，只是为了展示“它有效”

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

---

改进:无重复

最后，如 Turo 的代码所示

我们可以注意到我们可能有重复的候选人。

考虑S = 'aaaabc', A='aab', B='aac'。 消耗'aa'后:

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

这里我们按 AA、AB、BA、BB 的顺序排列。但是 AB 和 BA 都会导致候选 { iA: 1, iB: 1 }

因此，我们可以通过考虑哈希键 iA+''+iB 来缩小我们探索的空间状态并避免重复。

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"))