Word Composition

From a given list of strings, determine whether it can compose a target word with each word only allowed to extract at most one character.

example:

["abc", "bcd"] , target = "bb" => yes

["abc", "def"] , target = "ba" => no

Thoughts:

Think it as an bipartite matching problem to find the maximal matching number: if it equals the length of the target string, return true, else return false;

Code

// cin with strings
#include <iostream>
#include <string>
#include <vector>
#include <cstring>

using namespace std;

/**
 *From a given list of strings, determine whether it can compose a target word with
 * each word only allowed to extract at most one character.
 * example:
 * ["abc", "bcd"] , target = "bb" => yes
 * ["abc", "def"] , target = "ba" => no
 */
class WC {
    struct Edge {
        int from;
        int to;
        int weight;

        Edge(int f, int t, int w) : from(f), to(t), weight(w) {};
    };

    typedef vector<int>::iterator iterator_t;
    vector<string> words;
    string target;
    int _maxNodes;
    int num_left;
    vector<int> matching ;
    vector<int> check;
    vector<vector<int>> G;
    vector<Edge> edges;
public:
    WC(vector<string> w, string t) {
        words = w;
        num_left = static_cast<int>(w.size());
        cout<<num_left<< " " << t.size()<< endl;
        _maxNodes = static_cast<int>(w.size() + t.size());
        cout<<_maxNodes<< " _maxNodes" << endl;
        // assign some values:
        G.resize(_maxNodes);
        matching.resize(_maxNodes);
        check.resize(_maxNodes);
        fill(matching.begin(),matching.end(),-1);
        fill(check.begin(),check.end(),-1);
//        for (unsigned i=0; i<_maxNodes; i++) {matching[i]=-1; check[i]=0;}

        target = t;
        for(int i = 0; i < num_left; i++){
            for(int j = 0; j < t.size(); j++){
                if(words[i].find(t[j])!=string::npos) {
                    G[i].push_back(num_left+j); G[num_left+j].push_back(i);
                    edges.emplace_back(i, num_left+j, 0);
                    edges.emplace_back(num_left+j, i,0);
                }
            }
        }
        cout<<G.size()<<endl;
        cout<<" last vec in G: ";
        for(auto num: G[1]) cout<<num<<" ";
        cout<<endl;
        cout<<edges.size()<<endl;
    }

    int wordComposition(vector<string> words, string targets) {
        /* for(auto w: words) cout<<w<<" "<<endl;
         cout<<targets<<endl;
       */
       return hungarian();
    }

    bool dfs(int u) {
        for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点
            int v = *i;//edges[*i].to;
            if (!check[v]) {     // 要求不在交替路中
                check[v] = true; // 放入交替路
                if (matching[v] == -1 || dfs(matching[v])) {
                    // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功
                    matching[v] = u;
                    matching[u] = v;
                    return true;
                }
            }
        }
        return false; // 不存在增广路，返回失败
    }

    int hungarian(){
        int ans = 0;
//      memset(matching, -1, sizeof(matching));
        fill(matching.begin(), matching.end(), -1);
        for (int u=0; u < num_left; ++u) {
            if (matching[u] == -1) {
//              memset(check, 0, sizeof(check));
                fill(check.begin(), check.end(), 0);
                if (dfs(u)){
                    cout <<"matched val: "<<u<<endl;
                    ++ans;
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<string> words = {"cb","6","3", "last?","one", "with", "y", "i", "sa", "t","nn","re?", "hello"};
    string target = "c6?onewith";
    WC wc(words, target);
    int matchedNum = wc.wordComposition(words, target);
    cout<< "matchedNum: " <<matchedNum <<endl;
    bool ans = (target.size() == matchedNum );
    cout.setf(ios_base:: boolalpha);
    cout<< ans <<endl;

    return 0;
}