[Java] UVa 10100 Longest Match

題目連結

題意:
每組測資給兩行字串
比較兩字串依順序出現相同的單字數最多有多少
所謂的單字是指由英文字母或數字組成
例如:
777 888 99a.25
以上有 4 個單字，
(.非有效，99a 和 25 是兩個單字)

也就是最長共同子序列問題
Longest Common Subsequence (LCS)
只是元素從單個字元變成單字

解法:
如果以字元為單位
還要先分析哪裡到哪裡是有效單字
實作起來會很費力

所以乾脆先處理輸入測資，找出單字
用字串陣列 String[ ] 存每個單字
題目就真的能以 LCS 問題來解了

找出單字時，先將字串整理
非字母與數字的一律以空格取代
再用 split 方法切開，陣列就幫你存好材料了

解 LCS 時，判斷單字相同用 equals 方法比較
然後用 DP 找最大解
ff[i][j] 表示字串 1 到 i，字串 2 到 j 的位置當下的 LCS 長度

程式(Java):

	import java.util.*;
	public class Main {
	public static boolean isLetter(char c) {
	return ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'));
	}
	public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int cases = 1;
	while (sc.hasNext()) {
	System.out.printf("%2d. ",cases++);
	String S1 = sc.nextLine();
	String S2 = sc.nextLine();
	if (S1.length() == 0 || S2.length() == 0) {
	System.out.printf("Blank!\n");
	} else {
	StringBuilder sb = new StringBuilder();
	for (int i = 0; i < S1.length(); i++) {
	if (!isLetter(S1.charAt(i)))
	sb.append(" ");
	else
	sb.append(S1.charAt(i));
	}
	String s1[] = sb.toString().split(" ");
	sb = new StringBuilder();
	for (int i = 0; i < S2.length(); i++) {
	if (!isLetter(S2.charAt(i)))
	sb.append(" ");
	else
	sb.append(S2.charAt(i));
	}
	String s2[] = sb.toString().split(" ");
	int ff[][] = new int[s1.length+1][s2.length+1];
	for (int i = 1; i <= s1.length; i++)
	for (int j = 1; j <= s2.length; j++) {
	ff[i][j] = ff[i-1][j];
	if (ff[i][j] < ff[i][j-1])
	ff[i][j] = ff[i][j-1];
	if (s1[i-1].equals(s2[j-1]))
	ff[i][j] = ff[i-1][j-1] + 1;
	}
	System.out.printf("Length of longest match: %d\n", ff[s1.length][s2.length]);
	}
	}
	}
	}

view raw UVa10100.java hosted with ❤ by GitHub