Suppose a string Z is formed by interspersing the characters from other two strings X and Y. The new string Z is called a shuffle of X and Y if characters in Z com- ing from the same string still keep the order as in the original string. For example, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING: PRODGYRNAMAMMIINCG DYPRONGARMAMMICING Given three strings A[1..m], B[1..n], and C[1..m+n], design a dynamic programming algorithm to determine if C is a shuffle of A and B.
Suppose a string Z is formed by interspersing the characters from other two strings X and Y. The new string Z is called a shuffle of X and Y if characters in Z com- ing from the same string still keep the order as in the original string. For example, the strings PRODGYRNAMAMMIINCG and DYPRONGARMAMMICING are both shuffles of DYNAMIC and PROGRAMMING: PRODGYRNAMAMMIINCG DYPRONGARMAMMICING Given three strings A[1..m], B[1..n], and C[1..m+n], design a dynamic programming algorithm to determine if C is a shuffle of A and B.
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![Suppose a string \( Z \) is formed by interspersing the characters from two other strings \( X \) and \( Y \). The new string \( Z \) is called a shuffle of \( X \) and \( Y \) if characters in \( Z \) coming from the same string still keep the order as in the original string. For example, the strings "PRODGYRNAMAMMIINCG" and "DYPRONGARMAMMICING" are both shuffles of "DYNAMIC" and "PROGRAMMING":
\[ \text{PRODGYRNAMAMMIINCG} \]
\[ \text{DYPRONGARMAMMICING} \]
Given three strings \( A[1..m] \), \( B[1..n] \), and \( C[1..m+n] \), design a dynamic programming algorithm to determine if \( C \) is a shuffle of \( A \) and \( B \).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F95ffe1ad-d389-440c-9342-caff3016d161%2F58ce7f00-69cb-4089-a5b7-a096dca9c062%2Ff8n3bxr_processed.png&w=3840&q=75)
Transcribed Image Text:Suppose a string \( Z \) is formed by interspersing the characters from two other strings \( X \) and \( Y \). The new string \( Z \) is called a shuffle of \( X \) and \( Y \) if characters in \( Z \) coming from the same string still keep the order as in the original string. For example, the strings "PRODGYRNAMAMMIINCG" and "DYPRONGARMAMMICING" are both shuffles of "DYNAMIC" and "PROGRAMMING":
\[ \text{PRODGYRNAMAMMIINCG} \]
\[ \text{DYPRONGARMAMMICING} \]
Given three strings \( A[1..m] \), \( B[1..n] \), and \( C[1..m+n] \), design a dynamic programming algorithm to determine if \( C \) is a shuffle of \( A \) and \( B \).
Expert Solution
Algorithm
- Start with first characters of X, Y and Z.
- If first characters of X and Z matches, move 1 character forward of X and Z and check recursively.
- If first characters of Y and Z matches, move 1 character forward of Y and Z and check recursively.
- If X, Y and Z are empty return True.
- if any of the step 2 or step 3 returns True, return True.
Step by step
Solved in 2 steps
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY