logo标签列表

检查一个字符串是否是两个给定字符串的混合结果

stringalgorithmdynamic-programming
4
这是《算法设计手册》中的一个问题：
假设你有三个字符串：X，Y和Z，其中|X|=n，|Y|=m，|Z|= n+m。当且仅当Z可以通过以维护每个字符串中的从左到右字符顺序的方式交错X和Y的字符而形成时，称Z为X和Y的交错。请提供一种有效的动态规划算法来确定Z是否为X和Y的交错。
提示：您构造的动态编程矩阵的值应该是布尔值，而不是数值。
这是我尝试过的方法：
最初，我创建了一个1-D字符数组和指向X、Y、Z起始字符的指针。如果Z-pointer匹配X-pointer，则将X存储在字符数组中，否则使用Y-pointer进行检查。如果字符数组中的每个条目与其上一个条目不同，则Z不是交错的。
能否有人帮助我解决这个问题？
2
请展示一下你尝试过的内容。 - Abhishek Bansal
@Mörre 不，这不是我的作业。我只是引用了《算法设计手册》的内容。 - piyukr
如果你想得到一个好的回复，你必须自己付出一些努力。 - Abhishek Bansal
@AbhishekBansal。这是我尝试的方法：最初，我创建了一个1-D字符数组和指向X、Y、Z起始字符的指针。如果Z指针与X指针匹配，则将X存储在字符数组中，否则检查是否与Y指针相同。如果字符数组中的每个条目与其上一个条目不不同，则Z未交错。 - piyukr
7个回答
4

首先，让我们从一些定义开始。我用X[i]表示X的第i个元素，用X[i)表示以索引i开始的X子字符串。

例如，如果X = abcde，那么X[2] = c，X[2) = cde。

Y和Z的定义类似。

为了通过动态规划解决问题，您应该保留一个大小为(n+1) x (m+1)的二维布尔数组A。在这个数组中，当且仅当X[i)和Y[j)可以交错形成Z[i+j)时，A[i, j] = true。

对于任意的(i, j)，在二维数组的中间某个位置，递推关系非常简单：

A[i, j] := X[i] = Z[i+j] and A[i+1, j]
        or Y[j] = Z[i+j] and A[i, j+1]

在2D数组的边缘，要么X 要么 Y 已经到了它们的结尾，这意味着另一个后缀应该等于Z的后缀：

A[m, j] := Y[j) = Z[m+j)
A[i, n] := X[i) = Z[i+n)
A[m, n] := true

如果您首先填充数组的边界（对于所有i，j，即A[m, j]和A[i, n]），然后向A[0, 0]循环并适当地设置条目，最终A[0, 0]将是您的答案。

2
以下方法可以给您一个想法。
定义条件 d(s1,s2,s3) = (s1 + s2 == s3) { s3 是 s1 和 s2 的洗牌 } 我们需要找到 d(X,Y,Z)。
如果 s1 和 s2 的长度均为 1，且 s3 的长度为 2，
d( s1,s2,s3 ) = { (s1[0] == s3[0] && s2[0] == s3[1]) || (s1[0] == s3[1] && s2[0] == s3[0])

同样地，空字符串的 d 值可以获得。
对于任意长度的字符串，以下关系成立。
d( s1,s2,s3 ) = { ( d( s1-s1[last],s2,s3 - s3[last]) && s1[last] == s3[last] )
                  || ( d( s1,s2 - s2[last],s3 - s3[last]) && s2[last] == s3[last] )
                }

你可以从零长度的字符串开始计算d()条目，并持续检查。
交错不意味着Z中连续的字符必须交替来自X和Y吗？ - piyukr
不，交错只意味着Z应该包含X和Y中的所有字符，并且以它们在各自字符串中的顺序相同。例如，abc和def可以交错组合成abcdef。 - Abhishek Bansal
1

如果你使用Java来解决这个问题，我认为这非常容易。

基于Java的解决方案

public class ValidShuffle {

    public static void main(String[] args) {
   
        String s1 = "XY";
        String s2 = "12";

        String results = "Y21XX";
    
        validShuffle(s1, s2, results);

    }

    private static void validShuffle(String s1, String s2, String result) {
        
        String s3 = s1 + s2;
        StringBuffer s = new StringBuffer(s3);

        boolean flag = false;

        char[] ch = result.toCharArray();

        if (s.length() != result.length()) {
            flag = false;
        } else {

            for (int i = 0; i < ch.length; i++) {
                
                String temp = Character.toString(ch[i]);

                if (s3.contains(temp)) {

                    s = s.deleteCharAt(s.indexOf(temp));
                    s3 = new String(s);
                    flag = true;
                    
                } else {
                    flag = false;
                    break;
                }

            }

        }

        if (flag) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

    }

}

如果我的代码有任何问题，请在评论中告诉我。 谢谢。
1
它由以下递归关系定义：-
S(i,j,k) = false

if(Z(i)==Y(k))
  S(i,j,k) = S(i,j,k)||S(i+1,j,k+1)

if(Z(i)==X(j))
  S(i,j,k) = S(i,j,k)||S(i+1,j+1,k)

Where S(i,j,k) corresponds to Z[i to end] formed by shuffle of X[j to end] and Y[K to end]

你应该尝试自己将其编程为DP。

0
    function checkShuffle(str1, str2, str3) {
      var merge=str1+str2;
      var charArr1= merge.split("").sort();
      var charArr2= str3.split("").sort();
      for(i=0;i<str3.length;i++){
         if(charArr1[i] == charArr2[i]){
            return true; 
         }
      }    
     return false;
   }
checkShuffle("abc", "def", "dfabce"); //output is true
0

基于JavaScript的解决方案

 const first = "bac";
 const second = "def"
 const third = "dabecf";

function createDict(seq,str){
   let strObj = {};
   str = str.split("");
   str.forEach((letter,index)=>{
   strObj[letter] = {
       wordSeq: seq,
       index : index

   } ;
   })
   return strObj;
 }

function checkShuffleValidity(thirdWord,firstWord,secondWord){
    let firstWordDict = createDict('first',firstWord);
    let secondWordDict = createDict('second',secondWord);
    let wordDict = {...firstWordDict,...secondWordDict};
    let firstCount=0,secondCount = 0;
    thirdWord = thirdWord.split("");
    for(let i=0; i<thirdWord.length; i++){
        let letter = thirdWord[i];
         if(wordDict[letter].wordSeq == "first"){
      if(wordDict[letter].index === firstCount){
         firstCount++;
      }else{
        return false
      }        
    }else{
    if(wordDict[letter].index === secondCount){
      secondCount++;
    }else{
      return false;
    }

    }
}  
return true;
}

 console.log(checkShuffleValidity(third,first,second));
-1

关键点：

  1. 所有字符串都不应为空或空字符串。
  2. 前两个字符串长度之和应等于第三个字符串的长度。
  3. 第三个字符串不应包含前两个字符串的子字符串。
  4. 否则，创建字符数组，排序并比较。

代码：

public static boolean validShuffle(String first, String second, String third){
  boolean status=false;
  if((first==null || second==null || third==null) || (first.isEmpty()|| second.isEmpty() || third.isEmpty())){
    status = false;
  } else if((first.length()+second.length()) !=third.length()){
    //check if the sum of 2 lengths equals to the third string length
    status = false;
  } else if(third.indexOf(first,0)!=-1 || third.indexOf(second,0)!=-1){
    //check if the third string contains substrings
    status = false;
  } else {
    char [] c1_2=(first+second).toCharArray();
    char [] c3 =third.toCharArray();
    Arrays.sort(c1_2);
    Arrays.sort(c3);
    status=Arrays.equals(c1_2, c3);
  }
  return status;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接