ตรวจสอบว่าสตริงเป็นการสับเปลี่ยนของสตริงที่กำหนดอีกสองสตริงหรือไม่

แนวทางต่อไปนี้ควรให้แนวคิดแก่คุณ

กำหนดเงื่อนไข d(s1,s2,s3) = (s1 + s2 == s3) { s3 is a shuffle of s1 and 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() โดยเริ่มจากสตริงที่มีความยาวเป็นศูนย์และตรวจสอบต่อไป

ขั้นแรก เรามาเริ่มด้วยคำจำกัดความบางประการกันก่อน ฉันเขียน X[i] สำหรับองค์ประกอบ ith ของ X และ X[i) สำหรับสตริงย่อยของ X เริ่มต้นที่ดัชนี i

ตัวอย่างเช่น ถ้า X = abcde แล้วก็ X[2] = c และ X[2) = cde

คำจำกัดความที่คล้ายกันถือเป็น Y และ Z

ในการแก้ปัญหาด้วยการเขียนโปรแกรมแบบไดนามิก คุณควรเก็บอาร์เรย์บูลีน 2D A ขนาด (n+1) x (m+1) ไว้ ในอาร์เรย์นี้ A[i, j] = true ก็ต่อเมื่อ X[i) และ Y[j) สามารถแทรกลงในรูปแบบ Z[i+j) ได้

สำหรับ (i, j) ตามอำเภอใจ ที่ใดที่หนึ่งตรงกลางอาร์เรย์ 2D ความสัมพันธ์การเกิดซ้ำนั้นง่ายมาก:

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

หากคุณเติมเส้นขอบของอาร์เรย์ก่อน (A[m, j] และ A[i, n] สำหรับ i, j ทั้งหมด) คุณสามารถวนกลับไปที่ A[0, 0] และตั้งค่ารายการอย่างเหมาะสม ท้ายที่สุด A[0, 0] คือคำตอบของคุณ

มันถูกกำหนดโดยความสัมพันธ์ที่เกิดซ้ำดังต่อไปนี้: -

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 ด้วยตัวคุณเอง

โซลูชั่นที่ใช้ 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. สตริงทั้งหมดไม่ควรเป็นค่าว่างหรือว่างเปล่า
2. ผลรวมของความยาว 2 สายควรเท่ากับสายที่สาม
3. สตริงที่สามไม่ควรมีสตริงย่อยของ 2 สตริง
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;
}