結果

問題 No.225 文字列変更(medium)
コンテスト
ユーザー wahr69
提出日時 2015-08-05 14:19:14
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,382 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,219 ms
コンパイル使用メモリ 80,024 KB
実行使用メモリ 64,808 KB
最終ジャッジ日時 2024-07-18 03:30:23
合計ジャッジ時間 15,776 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import java.io.*;
import java.util.LinkedList;
import java.util.List;

public class no225 {
	
	static int N;
	static int M;
	static String S;
	static String T;
	
	// 終了したらfalseを返す
	public static boolean next(int[] indexes) {
		int i = indexes.length - 1;
		indexes[i] += 1;
		int count = 0;
		while (indexes[i] >= N - count) {
			if (i == 0) {
				return false;
			}
			indexes[i - 1] += 1;
			--i;
			++count;
		}
		for (int j = i + 1; j < indexes.length; ++j) {
			indexes[j] = indexes[j - 1] + 1;
		}
		return true;
	}
	
	public static boolean isCorrect(List<Character> a, String b) {
		int count = 0;
		for (Character c : a) { 
			if (!c.equals(b.charAt(count))) {
				return false;
			}
			++count;
		}
		return true;
	}
	
	public static int illiegalCharsCount(List<Character> a, String b) {
		int count = 0;
		int ret = 0;
		for (Character c : a) { 
			if (!c.equals(b.charAt(count))) {
				++ret;
			}
			++count;
		}
		return ret;
	}
	
	/**
	 * @param args
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		String[] input = r.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		M = Integer.parseInt(input[1]);
		S = r.readLine();
		T = r.readLine();
		
		String newS = S;
		if (M > N) {
			int temp = N;
			N = M;
			M = temp;
			
			String tempS = S;
			S = T;
			T = tempS;
		}
		
		if (N > M) {
			// 多い時、削除する
			int[] indexes = new int[N - M];
			for (int i = 0; i < N - M; ++i) {
				indexes[i] = i;
			}
			int min = 99999999;
			String minStr = "";
			boolean ret = true;
			while (ret) {
				List<Character> newStr = new LinkedList<Character>();
				int index = 0;
				for (int i = 0; i < N; ++i) {
					if (index < indexes.length && i == indexes[index]) {
						++index;
						continue;
					}
					newStr.add(S.charAt(i));
				}
				
				int illiegalCharsNum = illiegalCharsCount(newStr, T);
				if (illiegalCharsNum < min) {
					min = illiegalCharsNum;
					minStr = "";
					for (Character c : newStr) {
						minStr += c;
					}
				}
				
				ret = next(indexes);
			}
			
			newS = minStr;
		}
		
		// 文字列変更カウント
		int result = 0;
		for (int i = 0; i < M; ++i) {
			if (newS.charAt(i) != T.charAt(i)) {
				++result;
			}
		}
		
		System.out.println(result + Math.abs(N - M));
	}
	
}
0