You should provide a 'Dynamic Programming' algorithm to solve this problem. Dr. Watson has been kidnaped!...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You should provide a 'Dynamic Programming' algorithm to solve this problem. Dr. Watson has been kidnaped! Sherlock Holmes was contacted by the kidnapper for ransom. Moments later he received a message from Dr. Watson's phone. The message contained three random strings. Sherlock being Sherlock, was able to deduce immediately that Dr. Watson was trying to give a hint about his location. He figured out that the longest common subsequence between the 3 words is the location. But since it was too easy for him, he got bored and asked you to find out what the actual location is. Your task is to find the longest common subsequence from the 3 given strings before it is too late. Definitions: Subsequence - A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For instance, given a sequence "drew"; "d", "w", "de", "drw", "drew" are all examples of valid subsequences (there are also others), while "er", "wdre" are not. Note: W is a common subsequence of X, Y, and Z if and only if W is a subsequence of X, W is a subsequence of Y and W is a subsequence of Z. If a common subsequence does not exist, return "Does not exist" (without quotes) Your goal is to find the longest common subsequence, not just any common subsequence. Input Format Three lines, each containing a string. Note: Each string only contains lowercase English alphabet letters (i.e. a, b, ..., y, z). Constraints 1 1 import java.io.*; 2 import java.util.*; 3 4 public class Solution { Java 8 * XX 5 6- public static void main(String[] args) { 7 /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 8 } 9} You should provide a 'Dynamic Programming' algorithm to solve this problem. Dr. Watson has been kidnaped! Sherlock Holmes was contacted by the kidnapper for ransom. Moments later he received a message from Dr. Watson's phone. The message contained three random strings. Sherlock being Sherlock, was able to deduce immediately that Dr. Watson was trying to give a hint about his location. He figured out that the longest common subsequence between the 3 words is the location. But since it was too easy for him, he got bored and asked you to find out what the actual location is. Your task is to find the longest common subsequence from the 3 given strings before it is too late. Definitions: Subsequence - A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For instance, given a sequence "drew"; "d", "w", "de", "drw", "drew" are all examples of valid subsequences (there are also others), while "er", "wdre" are not. Note: W is a common subsequence of X, Y, and Z if and only if W is a subsequence of X, W is a subsequence of Y and W is a subsequence of Z. If a common subsequence does not exist, return "Does not exist" (without quotes) Your goal is to find the longest common subsequence, not just any common subsequence. Input Format Three lines, each containing a string. Note: Each string only contains lowercase English alphabet letters (i.e. a, b, ..., y, z). Constraints 1 1 import java.io.*; 2 import java.util.*; 3 4 public class Solution { Java 8 * XX 5 6- public static void main(String[] args) { 7 /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 8 } 9}
Expert Answer:
Related Book For
Introduction to Management Science A Modeling and Cases Studies Approach with Spreadsheets
ISBN: 978-0078024061
5th edition
Authors: Frederick S. Hillier, Mark S. Hillier
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Peter, Emma, and Kyler played chess with each other. Peter won 4 games and lost 2 games. Emma won 3 games and lost 3 games. If Kyler lost 3 games, how many games did he win?
-
What is conservation? Preservation? How do they differ?
-
What role does supplier relationship management play in fostering strategic partnerships and collaborative innovation within supply networks, particularly in industries characterized by rapid...
-
What are the advantages and disadvantages of e-learning?
-
The following selected financial data pertain to four unidentified companies: This financial information pertains to the following companies: a. Full-line department store b. Wholesale fish company...
-
Selling expenses Direct labor Interest expense Manufacturing overhead, actual Raw materials used Administrative expenses $ 159,200 304,000 40,900 112,240 484,000 115,100 During the month, 18,600...
-
A company is using extract, transform, load (ETL) techniques to collect large volumes of medical encounters. Its purpose is to build models that can determine whether a certain patient is at risk of...
-
When measuring for quality, 100% inspection processes are generally expensive and not practical for business performance. Compare and contrast common sampling approaches (Simple random, stratified,...
-
What do you believe to be the most common reason for why some risks are not identified in projects? Why is that? Also include a situation in your place of work or daily life where a serious incident...
-
Explain what you think would happen if there was error in Mitosis?
-
Introduce nontraditional project management (PM) frameworks. Describe the characteristics in the organization that support an adaptive project management (APM) approach. Analyze three nontraditional...
-
What is merchantability? What is an example of merchantability?
-
Go to the website www.fda.gov/opacom/laws/fdact/fdctoc.htm and write a paper in which you need to address the following: 1. What is the name of the organization or entity whose site it is you are...
-
Ann hires a nanny to watch her two children while she works at a local hospital. She pays the 19 year-old nanny $125 per week for 48 weeks during the current year. a. What is the employers portion of...
-
In the electric field pattern for a sinusoidally oscillating dipole shown in Figure 30. 21, what are (a) the direction of the change in the electric field \(\Delta \vec{E}\) at point \(\mathrm{C}\)...
-
The magnitude of the electric field of Figure P30.1 is changing with time. As a result of this change, there is an upward-pointing magnetic field at position \(\mathrm{P}\). Is the electric field...
-
Figure P30.2 shows two electric fields, one in a region of circular cross-section and one in a long flat region. In both cases, the electric field decreases over time. What is the direction of the...
Study smarter with the SolutionInn App