ring def imp sep content hat jin ted
Given two strings a and b of equal length, what's the longest string (S) that can be constructed such that S is a child to both a and b.
String x is said to be a child of string y if x can be formed by deleting 0 or more characters from y
Input format
Two strings a and b with a newline separating them
Constraints
All characters are upper-cased and lie between ascii values 65-90The maximum length of the strings is 5000
Output format
Length of the string S
Sample Input #0
- HARRY
- SALLY
Sample Output #0
- 2
The longest possible subset of characters that is possible by deleting zero or more characters from HARRY and SALLY is AY, whose length is 2.
Sample Input #1
- AA
- BB
Sample Output #1
- 0
AA and BB has no characters in common and hence the output 0
Sample Input #2
- SHINCHAN
- NOHARAAA
Sample Output #2
- 3
The largest set of characters, in order, between SHINCHAN and NOHARAAA is NHA.
Sample Input #3
- ABCDEF
- FBDAMN
Sample Output #3
- 2
- import java.util.Scanner;
- import java.lang.String;
- import java.lang.Math;
- /*
- class TreeNode
- {
- int val;
- TreeNode left;
- TreeNode right;
- TreeNode(int x) { val = x; left = null; right = null;}
- }
- class ListNode
- {
- int val;
- ListNode next;
- ListNode(int x){val = x; next = null;}
- }
- */
- public class Solution {
- public static void main(String[] args)
- {
- //int T;
- Scanner jin = new Scanner(System.in);
- //T = jin.nextInt();
- String str1 = jin.next();
- String str2 = jin.next();
- int len = str1.length();
- int[][] array = new int[len+1][len+1];
- for(int i = 0; i < len+1; i++)
- array[0][i] = array[i][0] = 0;
- for(int i = 0; i < len; i++)
- {
- for(int j = 0; j < len; j++)
- {
- if (str1.charAt(i) == str2.charAt(j)) {
- array[i+1][j+1] = array[i][j] + 1;
- }
- else {
- array[i+1][j+1] = Math.max(array[i][j+1], array[i+1][j]);
- }
- }
- }
- System.out.println(array[len][len]);
- array = null;
- }
- }
【HackerRank】Common Child (LCS) 最长公共子序列
来源: http://www.bubuko.com/infodetail-2063982.html