NO CODING NO LIFE: BFS

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

Have you met this question in a real interview?

Yes

Example

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Tags Expand

Breadth First Search

Codes and thought reference:;

http://bangbingsyb.blogspot.com/2014/11/leetcode-word-ladder-i-ii.html

s1: insert end string into dict
s2: BFS adjacent nodes from start string

About adjacent node: Here is to get string that has only one different digit;
Compare length of the string to get adjacent strings is w
One way is to search the whole dictionary and get string with only one different digit O(n*w)
Second way is to get all strings with one different digit O(26*w)
When dictionary is large, we have to use second way

Time: O(E)
Space: O(V)

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // write your code here
        dict.insert(end);
        queue<pair<string, int> > Q;
        Q.push(make_pair(start, 1));
        while(!Q.empty()){
            string s = Q.front().first;
            int len = Q.front().second;
            Q.pop();
            if(s == end) return len;
            findNeibors(Q, s, len, dict);
        }
        return 0;
    }
    void findNeibors(queue<pair<string, int> > &Q, string s, int len, unordered_set<string> &dict){
        vector<string> neibors;
        for(int i = 0; i < s.length(); i++){
            char c = s[i];
            for(int j = 0; j < 26; j++){
                s[i] = 'a' + j;
                if(s[i] == c) continue;
                if(dict.count(s)) {
                    neibors.push_back(s);
                    dict.erase(s);
                }
            }
            s[i] = c; //DON"T FORGET
        }
        for(int i = 0; i < neibors.size(); i++){
            Q.push(make_pair(neibors[i], len + 1));
        }
    }
};

Lintcode second:

class Solution {
public:
    /**
      * @param start, a string
      * @param end, a string
      * @param dict, a set of string
      * @return an integer
      */
    int ladderLength(string start, string end, unordered_set<string> &dict) {
        // write your code here
        queue<string> Q;
        if(start == "") return 0;
        Q.push(start);
        int size = 1;
        int curLevel = 1;
        while(!Q.empty()){
            string cur = Q.front();
            Q.pop();
            size--;
            if(cur == end) return curLevel;
            
            //find neighbors and add them to Q
            for(int i = 0; i < cur.size(); i++){
                char c = cur[i];
                for(int j = 0; j < 26; j++){
                    if(c == 'a' + j) continue;
                    cur[i] = 'a' + j;
                    if(dict.count(cur)) {
                        Q.push(cur);
                        dict.erase(cur); //Don't forget
                    }
                }
                cur[i] = c; //dong't forget
            }
            //update level
            if(size == 0){
                size = Q.size();
                curLevel++;
            }
            
        }
        return 0;
    }
};

Given an directed graph, a topological order of the graph nodes is defined as follow:

For each directed edge A -> B in graph, A must before B in the order list.
The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Have you met this question in a real interview?

Yes

Example

For graph as follow:

The topological order can be:

[0, 1, 2, 3, 4, 5]
[0, 2, 3, 1, 5, 4]
...

Note

You can assume that there is at least one topological order in the graph.

Challenge

Can you do it in both BFS and DFS?

Tags Expand

LintCode Copyright Geeks for Geeks Depth First Search Breadth First Search

九章算法DFS
//both BFS and DFS
http://algorithm.yuanbin.me/zh-cn/graph/topological_sorting.html
//good BFS version
http://meetqun.com/thread-5526-1-1.html

Topological sort is for DAG(Directed acyclic graph)

indgree makes sure the topological order and vertices will not be counted repeatedly.

BFS solution:
s1: calc indegree of all vertices
s2: get the origin(vertice with 0 indegree) and push it into queue
s3: While queue is not empty:
pop the front element as cur and push it into result vector
for cur adjacent vertices:
minus its indegree by 1;
if its indegree equals to 0, push this vertice to result vector

Time: O(V+E)
s1-- O(V+E)
s2-- O(V)
s3-- O(V+E)
Space:O(V)

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        queue<DirectedGraphNode*> q;
        bfs(graph, indegree, q, res);
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void bfs(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree, queue<DirectedGraphNode*> &q, vector<DirectedGraphNode*> &res){
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) {
                q.push(graph[i]);
                //res.push_back(graph[i]);
            }
        }
        while(!q.empty()){
            DirectedGraphNode* cur = q.front();
            res.push_back(cur);
            q.pop();
            for(int i = 0; i < cur->neighbors.size(); i++){
                indegree[cur->neighbors[i]]--;
                if(indegree[cur->neighbors[i]] == 0) q.push(cur->neighbors[i]);
            }
        }
    }
};

DFS solution 1:
Not real DFS, actually just like BFS, use stack replace the queue in BFS solution
s1: calc indegree of all vertices
s2: DFS the vertice with 0 indegree
s3: DFS( minus adjacent vertices' indegrees by 1, if any vertice indegree is 0, bfs this vertice)

O(V+E)

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) DFS(indegree, graph[i], res);
        }
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                /*if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;*/
                indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void DFS(unordered_map<DirectedGraphNode*, int> &indegree, DirectedGraphNode* node, vector<DirectedGraphNode*>& res){
        indegree[node]--;
        res.push_back(node);
        for(int i = 0; i < node->neighbors.size(); i++){
            indegree[node->neighbors[i]]--;
            if(indegree[node->neighbors[i]] == 0) DFS(indegree, node->neighbors[i], res);
        }
    }
};

DFS solution 2:
Used a stack to record DFS order and pint the stack
In DFS, we push current node in stack in the end

a vertex is pushed to stack only when all of its adjacent vertices (and their adjacent vertices and so on) are already in stack.

//thought reference:
http://www.geeksforgeeks.org/topological-sorting/
//thought / process /codes reference
https://www.youtube.com/watch?v=jksMzq4LgfM

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //look for the head node
        vector<DirectedGraphNode*> res;
        if(!graph.size()) return res;
        //get indegree    
        unordered_map<DirectedGraphNode*, int> indegree;
        indeg(graph, indegree);
        //push nodes with 0 indegree and pop to result;
        unordered_set<DirectedGraphNode*> mark;
        stack<DirectedGraphNode*> s;
        for(int i = 0; i < graph.size(); i++){
            if(indegree[graph[i]] == 0) DFS(mark, graph[i], s);
        }
        while(!s.empty()){
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
private:
    void indeg(vector<DirectedGraphNode*> &graph, unordered_map<DirectedGraphNode*, int> &indegree){
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                /*if(!indegree.count(graph[i]->neighbors[j])) indegree[graph[i]->neighbors[j]] = 1;
                else indegree[graph[i]->neighbors[j]]++;*/
                indegree[graph[i]->neighbors[j]]++;
            }
        }
    }
    void DFS(unordered_set<DirectedGraphNode*> &mark, DirectedGraphNode* node, stack<DirectedGraphNode*> &s){
        mark.insert(node);
        for(int i = 0; i < node->neighbors.size(); i++){
            if(!mark.count(node->neighbors[i])) DFS(mark, node->neighbors[i], s);
        }
        s.push(node);
    }
};

Lintcode second:

/**
 * Definition for Directed graph.
 * struct DirectedGraphNode {
 *     int label;
 *     vector<DirectedGraphNode *> neighbors;
 *     DirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */
    vector<DirectedGraphNode*> topSort(vector<DirectedGraphNode*> graph) {
        // write your code here
        //get indegrees
        unordered_map<DirectedGraphNode*, int> indegrees;
        for(int i = 0; i < graph.size(); i++){
            for(int j = 0; j < graph[i]->neighbors.size(); j++){
                indegrees[graph[i]->neighbors[j]]++;
            }
        }
        //get head
        queue<DirectedGraphNode*> q;
        for(int i = 0; i < graph.size(); i++){
            if(indegrees[graph[i] ] == 0) q.push(graph[i]);
        }
        //start sort
        vector<DirectedGraphNode*> res;
        while(!q.empty()){
            DirectedGraphNode* cur = q.front();
            res.push_back(cur);
            q.pop();
            for(int i = 0; i < cur->neighbors.size(); i++){
                indegrees[cur->neighbors[i]]--;
                if(indegrees[cur->neighbors[i]] == 0) q.push(cur->neighbors[i]);
            }
        }
        return res;
    }
};

NO CODING NO LIFE

2015年9月19日星期六

Lintcode: Word Ladder

2015年9月18日星期五

Lintcode: Topological Sorting