ワード変換

コード#コード#

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isused[51];
int ans;
bool res;
/* 2개의 문자열이 알파벳 1개만 차이나는지 검사 */
bool check(string cur, string target){
    int cnt=0;
    for(int i=0;i<cur.length();i++)
        if(cur[i] != target[i]) cnt++;
    if(cnt == 1) return true;
    return false;
}
void DFS(int num, string cur, string target, vector<string>& words){
    if(check(cur, target)){
        ans=min(ans,num+1);
        return;
    }
    for(int i=0;i<words.size();i++)
    {
        if(isused[i]) continue;
        if(!check(cur, words[i])) continue;
        isused[i] = true;
        DFS(num+1, words[i], target, words);
        isused[i] = false;
    }
}
int solution(string begin, string target, vector<string> words) {
    ans = words.size();
    /* Words에 target이 없으면 어차피 못찾으니까 return 0; */
    auto it = find(words.begin(), words.end(), target);
    if(it == words.end()) return 0;
    /* 백트래킹 시작 */
    DFS(0, begin, target, words);
    return ans;
}