#include <iostream>
#include <queue>
#include <unordered_set>
#include <string>
using namespace std;

// 存储当前状态:当前的S和H
struct State {
    string s;
    string h;
    
    State(string s_, string h_) : s(s_), h(h_) {}
};

// 为State结构体实现哈希函数,用于unordered_set
struct StateHash {
    size_t operator()(const State& state) const {
        return hash<string>()(state.s) ^ (hash<string>()(state.h) << 1);
    }
};

// 为State结构体实现相等比较,用于unordered_set
struct StateEqual {
    bool operator()(const State& a, const State& b) const {
        return a.s == b.s && a.h == b.h;
    }
};

bool canTransform(string S, string T, string H) {
    // 边界情况处理
    if (S == T) return true;
    // 如果S长度小于T,不可能变换成功
    if (S.length() < T.length()) return false;
    // 如果目标T为空,只要移除S所有字符即可
    if (T.empty()) return true;
    
    // BFS队列和已访问集合
    queue<State> q;
    unordered_set<State, StateHash, StateEqual> visited;
    
    // 初始化队列
    q.push(State(S, H));
    visited.insert(State(S, H));
    
    while (!q.empty()) {
        State current = q.front();
        q.pop();
        
        // 如果当前S的长度小于T,无法继续操作
        if (current.s.length() < T.length()) continue;
        
        // 操作1:将首字母移到H前面
        string newS1 = current.s.substr(1);  // 移除首字母后的S
        string newH1 = current.s[0] + current.h;  // 首字母移到H前面
        if (newS1 == T) return true;
        
        State next1(newS1, newH1);
        if (visited.find(next1) == visited.end()) {
            q.push(next1);
            visited.insert(next1);
        }
        
        // 操作2:将尾字母移到H前面
        string newS2 = current.s.substr(0, current.s.size() - 1);  // 移除尾字母后的S
        string newH2 = current.s.back() + current.h;  // 尾字母移到H前面
        if (newS2 == T) return true;
        
        State next2(newS2, newH2);
        if (visited.find(next2) == visited.end()) {
            q.push(next2);
            visited.insert(next2);
        }
    }
    
    // 遍历所有可能状态后仍未找到目标
    return false;
}

int main() {
    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        string S, T, H;
        cin >> S >> T >> H;
        
        if (canTransform(S, T, H)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    
    return 0;
}


0 条评论

目前还没有评论...

信息

ID
116
时间
1000ms
内存
256MiB
难度
8
标签
递交数
56
已通过
9
上传者