はじめに
- 解けるまでの時間: 25分
- WA(TLE) 1回
問題
あなたはUnixにsedコマンドというものがある。
これは入力した文字列を書き換えるコマンドである。
例えば、aa を bca に書き換えるsedを aaxaaa という文字列に適用した場合、
書き換えた後の文字列は bcaxbcaa となる。
aaa の部分に関しては、aa の取り方が2パターン考えられるが、
このような場合は左から貪欲にマッチングされる。
(a, b) の組み合わせがn個と、s,tが与えられるので、 aをbにするsedを最低何回行えばsをtに変換できるか求めよ。
制約条件
- nは10以下
- a, b の長さは1以上10以下
- |a| <= |b|
- それぞれのaのはすべて異なる
- s, t の長さは1以上10以下
- |s| <= |t|
- 文字列は英語小文字のみを含む
解法
- 基本的に幅優先探索を行う
- 変換の制約条件から、置換したら文字列が短くなることはない
- 置換前と置換後で文字列が変化している
- ↑の2つで枝刈り&「変換することができない」判定を行う
- sedのシミュレートはJavaのreplaceAllを使うと楽
ソースコード
``java class Main { public static void main(String args) throws Exception { // System.out.println("aaxaaa".replaceAll("aa", "cba")); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); while(true) { int n = Integer.parseInt(br.readLine()); if(n == 0) break; String sed = new String[n]; for(int i = 0; i < n; i++){ sed[i] = br.readLine().split(" "); } // ゴール String s = br.readLine(); String g = br.readLine(); System.out.println(bfs(s, g, sed)); } }
static int bfs(String s, String g, String[][] sed){
if(s.equals(g)) return 0;
int n = sed.length;
// 最初の状態
State startState = new State(s, 0);
ArrayDeque<State> q = new ArrayDeque<State>();
q.addLast(startState);
// 幅優先探索
while(q.size() > 0) {
State state = q.pollFirst();
for (int i = 0; i < n; i++) {
String newStr = state.str.replaceAll(sed[i][0], sed[i][1]);
// ゴールしていた場合
if(newStr.equals(g)) {
return state.count + 1;
}
// ゴールの文字列より長くならない, 元の文字列から変化している
if(newStr.length() < g.length() && !newStr.equals(state.str)) {
q.addLast(new State(newStr, state.count + 1));
}
}
}
return -1;
}
}
