スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

回文作成最小操作数を返すクラス作成

/**
* 修正履歴
* 1からやりなおし! 2009/5/11
*/
package jp.co.namadanjo.topcoder;

public class PalindromeFactory {

public static void main(String[] args) {
PalindromeFactoryOld palindromeFactory = new PalindromeFactoryOld();
System.out.println(args[0] + "を回文にするためには"
+ palindromeFactory.getEditDistance(args[0])
+ "回の操作が必要");
}

/**
* 与えられた引数を回文にするために、必要な操作数の最小値を返すメソッド。
* 操作は
* 1. 文字の削除
* 2. 文字の追加
* 3. 文字の置換
* 4. 文字の入れ替え
* の4通り。ただし、4の入れ替えについては1度しかできない。
* @param initial 文字列
* @return 何操作で回文にできるか、最小値
*/
public int getEditDistance(String initial) {
char[] chars = initial.toCharArray();
int length = initial.length();
// イテレーター
int i, j;
// 最小操作数を格納する配列
int[][] minBox = new int[length][length];

// TODO 文字の置換については後で使用を追加

// iとjの初期化 文字列の中央にインデックスを設定
if (length % 2 == 1) {
// lengthが奇数の場合、中心の1文字だけを取得
i = length / 2;
j = i;
minBox[i][i] = 0;
} else {
// lengthが偶数の場合、中心の2文字を取得
i = length / 2 - 1;
j = length / 2;
if (chars[i] == chars[j]) {
// 偶数の場合でiとjの文字が同じ場合は0
minBox[i][j] = 0;
minBox[i][i] = 0;
minBox[j][j] = 0;
} else {
// 偶数の場合でiとjの文字が異なる場合は0
minBox[i][j] = 1;
minBox[i][i] = 0;
minBox[j][j] = 0;
}
}

// initialのi文字目からj文字目までの文字列を
// 回文にするための最小操作数をminBox[i][j]とすると、
// i文字目とj文字目が同じ場合
// minBox[i][j] = minBox[i+1][j-1]
// i文字目とj文字目が異なる場合
// j文字目を置換 : minBox[i+1][j]に1操作
// i文字と同じ文字を追加またはi文字を削除 : minBox[i+1][j-1]に1操作
//  minBox[i,j] = min(minBox[i+1][j] + 1,minBox[i+1][j-1]+1)
for (; i >= 0; i--) {

if (chars[i] == chars[j]) {
minBox[i][j] = minBox[i + 1][j - 1];
} else {
if (minBox[i + 1][j] < minBox[i + 1][j - 1]) {
minBox[i][j] = minBox[i + 1][j] + 1;
} else {
minBox[i][j] = minBox[i + 1][j - 1] + 1;
}
}
j++;
if (chars[i] == chars[j]) {
minBox[i][j] = minBox[i + 1][j - 1];
} else {
if (minBox[i + 1][j] < minBox[i + 1][j - 1]) {
minBox[i][j] = minBox[i + 1][j] + 1;
} else {
minBox[i][j] = minBox[i + 1][j - 1] + 1;
}
}
}

return minBox[0][length - 1];
}
}
スポンサーサイト
義援金募集
FC2「東北地方太平洋沖地震」義援金募集につきまして
プロフィール

生男女

Author:生男女
ニコ生で生放送やっている日ハムファンのさちえと太郎です。

コミュはこちらです。

最新記事
カテゴリ
検索フォーム
RSSリンクの表示
リンク
食べログ
QRコード
QRコード
月別アーカイブ
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。