Blocks to Spell Word - Google Top Interview Questions

                        Solution in C++ :

struct Graph {
    // number of verticies
    int V;
    // number of removed verticies
    int removed;
    // adjacency list
    list<int>* adjs;
    // rem[i] = true if node i was removed from graph
    bool* rem;

    Graph(int V) {
        this->V = V;
        removed = 0;
        adjs = new list<int>[V];
        rem = new bool[V];
    }

    void addEdge(int vFrom, int vTo) {
        adjs[vFrom].push_back(vTo);
    }

    // removes a directed edge
    void removeEdge(int vFrom, int vTo) {
        // iterate to find vTo in vFrom's adjacency list
        for (list<int>::iterator it2 = adjs[vFrom].begin(); it2 != adjs[vFrom].end(); ++it2) {
            // found vTo in vFrom's adjacency list
            if (*it2 == vTo) {
                adjs[vFrom].erase(it2);
                removed += (rem[vFrom] = adjs[vFrom].empty());  // true if vFrom now has degree 0
                break;
            }
        }
    }
    void print() {
        for (int i = 0; i < V; ++i) {
            cerr << '
' << i << "-> ";
            if (rem[i]) continue;
            for (const int& adj : adjs[i]) cerr << adj << ", ";
        }
        cerr << '
';
    }
};

bool solve(vector<string>& words, string target) {
    const int W = words.size(), T = target.size();
    if (words.size() < target.length()) return false;

    // bipartite graph
    Graph g(W + T);
    // the degree of the node with the smallest degree
    int min_degree = INT_MAX, n1;
    // iterate over all words and form edges
    for (int i = 0; i < W; ++i) {
        for (int t = 0; t < T; ++t) {
            if (words[i].find(target[t]) != -1) {
                g.addEdge(i, W + t);
                g.addEdge(W + t, i);
            }
        }
        if (0 < g.adjs[i].size() && g.adjs[i].size() < min_degree) {
            min_degree = g.adjs[i].size();
            n1 = i;
        }
    }

    // removing words that cannot contribute to the target
    // returning false if a target character could not be found
    for (int i = 0; i < g.V; ++i) {
        g.removed += (g.rem[i] = g.adjs[i].empty());
        // if a letter in the target could not find a match in words
        if (i > W && g.rem[i]) return false;
    }

    // cerr << "start conditions";
    // g.print();
    int pairs = 0;
    int itr = 0;
    // while not all edges have been removed
    while (g.removed != g.V) {
        // n1's first neighbor
        int n2 = *g.adjs[n1].begin();
        // mark nodes n1 and n2 as removed and remove edges from other nodes pointing to them
        g.rem[n1] = true;
        g.rem[n2] = true;
        g.removed += 2;
        // cerr << '
' << "match " << ++itr << ": (" << min(n1, n2) << ", " << max(n1,n2) << ')';
        // g.print();
        // disconnect all edges n->n1
        for (int n = 0; n < g.V; ++n)
            if (!g.rem[n]) g.removeEdge(n, n1);
        // disconnect all edges n->n2
        // and calculate new min_degree and n1
        min_degree = INT_MAX;
        for (int n = 0; n < g.V; ++n) {
            if (g.rem[n]) continue;
            g.removeEdge(n, n2);
            if (!g.rem[n] && 0 < g.adjs[n].size() && g.adjs[n].size() < min_degree) {
                min_degree = g.adjs[n].size();
                n1 = n;
            }
        }
        // indicate a new pair was made
        ++pairs;
    }
    return pairs == T;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public boolean solve(String[] words, String target) {
        int N = words.length;
        int M = target.length();
        boolean[][] dp = new boolean[1 << M][N + 1];
        dp[0][0] = true;
        for (int bit = 0; bit < (1 << M); bit++) {
            for (int i = 1; i <= N; i++) {
                dp[bit][i] = dp[bit][i - 1];
                for (int j = 0; j < M; j++) {
                    if ((bit & (1 << j)) > 0) {
                        String use = Character.toString(target.charAt(j));
                        if (words[i - 1].contains(use))
                            dp[bit][i] |= dp[bit - (1 << j)][i - 1];
                    }
                }
            }
        }
        return dp[(1 << M) - 1][N];
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, words, target):
        @cache
        def go(i, mask):
            if i == len(target):
                return True

            for j, x in enumerate(words):
                if (mask & (1 << j)) == 0 and target[i] in x:
                    if go(i + 1, mask | (1 << j)):
                        return True

            return False

        return go(0, 0)