[LeetCode] WordBreak II, Solution

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

[Thoughts]

既然是要给出所有解，那就递归好了，但是递归的过程中注意剪枝。

 

[Code]

没有剪枝版

 1     vector<string> wordBreak(string s, unordered_set<string> &dict) {
 2         string result;
 3         vector<string> solutions;
 4         int len = s.size();        
 5         GetAllSolution(0, s, dict, len, result, solutions);
 6         return solutions;
 7     }
 8     
 9     void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions)
10     {
11         if (start == len)
12         {
13             solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space
14             return;
15         }
16         for (int i = start; i< len; ++i)
17         {
18             string piece = s.substr(start, i - start + 1);
19             if (dict.find(piece) != dict.end() && possible[i+1])
20             {
21                 result.append(piece).append(" ");                
22                 GetAllSolution(i + 1, s, dict, len, result, solutions);                
23                 result.resize(result.size() - piece.size()-1);
24             }
25         }
26     }

但是很明显，这种裸的递归，效率太低，因为有大量的重复计算，肯定过不了测试数据。

剪枝版

这里加上一个possible数组，如同WordBreak I里面的DP数组一样，用于记录区间拆分的可能性

Possible[i] = true 意味着 [i,n]这个区间上有解

加上剪枝以后，运行时间就大大减少了。（Line 5, 20, 23, 25,26为剪枝部分）

 1     vector<string> wordBreak(string s, unordered_set<string> &dict) {
 2         string result;
 3         vector<string> solutions;
 4         int len = s.size();
 5         vector<bool> possible(len+1, true); // to record the search which has been executed once
 6         GetAllSolution(0, s, dict, len, result, solutions, possible);
 7         return solutions;
 8     }
 9     
10     void GetAllSolution(int start, const string& s, const unordered_set<string> &dict, int len, string& result, vector<string>& solutions, vector<bool>& possible)
11     {
12         if (start == len)
13         {
14             solutions.push_back(result.substr(0, result.size()-1));//eliminate the last space
15             return;
16         }
17         for (int i = start; i< len; ++i)
18         {
19             string piece = s.substr(start, i - start + 1);
20             if (dict.find(piece) != dict.end() && possible[i+1]) // eliminate unnecessory search
21             {
22                 result.append(piece).append(" ");
23                 int beforeChange = solutions.size();
24                 GetAllSolution(i + 1, s, dict, len, result, solutions, possible);
25                 if(solutions.size() == beforeChange) // if no solution, set the possible to false
26                     possible[i+1] = false;
27                 result.resize(result.size() - piece.size()-1);
28             }
29         }
30     }

suoyi

[FaceBook] Hanoi Moves, Solution

There are K pegs. Each peg can hold discs in decreasing order of radius when looked from bottom to top of the peg. There are N discs which have radius 1 to N; Given the initial configuration of the pegs and the final configuration of the pegs, output the moves required to transform from the initial to final configuration. You are required to do the transformations in minimal number of moves.
A move consists of picking the topmost disc of any one of the pegs and placing it on top of anyother peg.
At anypoint of time, the decreasing radius property of all the pegs must be maintained.

Constraints:
1<= N<=8
3<= K<=5


Input Format:
N K
2nd line contains N integers.
Each integer in the second line is in the range 1 to K where the i-th integer denotes the peg to which disc of radius i is present in the initial configuration.
3rd line denotes the final configuration in a format similar to the initial configuration.

Output Format:
The first line contains M - The minimal number of moves required to complete the transformation.
The following M lines describe a move, by a peg number to pick from and a peg number to place on.
If there are more than one solutions, it's sufficient to output any one of them. You can assume, there is always a solution with less than 7 moves and the initial confirguration will not be same as the final one.

Sample Input #00:

2 3
1 1
2 2
Sample Output #00:

3
1 3
1 2
3 2


Sample Input #01:
6 4
4 2 4 3 1 1
1 1 1 1 1 1
Sample Output #01:
5
3 1
4 3
4 1
2 1
3 1
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
If you are using "Java", the classname is "Solution"


[Thoughts]
No good idea, only brute-force can hit my mind now. seems a simple question, but the implementation really costs me some time.

Update: some people talk about using tree to do the BFS (http://comments.gmane.org/gmane.comp.programming.algogeeks/30920) or A* search (http://en.wikipedia.org/wiki/A*_search_algorithm). But I would say this is a bit over engineering.


[Code]

1:  /*  
2:  Please write complete compilable code.  
3:  Read input from standard input (STDIN) and print output to standard output(STDOUT).  
4:  For more details, please check https://www.interviewstreet.com/recruit/challenges/faq/view#stdio  
5:  */  
6:  #include <climits>  
7:  #include <iostream>  
8:  using namespace std;   
9:  int initial[9];  
10:  int expected[9];  
11:  int CurDiscInPeg[9];  
12:  int n, k;  
13:  int moveSeq[9][2];  
14:  int minSteps = 7;  
15:  int minMoveSeq[9][2];  
16:  void refreshPeg()  
17:  {  
18:    for(int i =1; i<= k; i++)  
19:    {  
20:      CurDiscInPeg[i] = INT_MAX; //no disk on it.  
21:      for(int j =1; j<=n; j++)  
22:      {  
23:        if(initial[j] == i)  
24:        {  
25:          CurDiscInPeg[i] =j;  
26:          break;  
27:        }  
28:      }  
29:    }  
30:  }  
31:  bool verify(int depth)  
32:  {  
33:    int z = 1;  
34:    for(; z<=n; z++)  
35:    {  
36:      if(initial[z]!=expected[z])  
37:        return false;  
38:    }  
39:    minSteps = depth;  
40:    for(int z = 1; z<=minSteps; z++)  
41:    {  
42:      minMoveSeq[z][0] = moveSeq[z][0];  
43:      minMoveSeq[z][1] = moveSeq[z][1];  
44:    }       
45:    return true;        
46:  }  
47:  void Move(int depth)  
48:  {  
49:    if(depth > minSteps) return;  
50:    for(int i =1; i<=k; i++)  
51:    {  
52:      for(int j=1; j<=k; j++)  
53:      {  
54:        if(CurDiscInPeg[i] >= CurDiscInPeg[j])  
55:          continue;  
56:        int disc = CurDiscInPeg[i];  
57:        initial[disc] = j;  
58:        moveSeq[depth][0] = i;  
59:        moveSeq[depth][1] = j;  
60:        if(verify(depth)) return;  
61:        refreshPeg();  
62:        Move(depth+1);  
63:        initial[disc] = i;  
64:        refreshPeg();  
65:      }  
66:    }  
67:  }  
68:  int main()  
69:  {  
70:    cin>>n;  
71:    cin>>k;  
72:    for(int i =1; i<=n; i++)  
73:    {  
74:      cin>>initial[i];  
75:    }  
76:    for(int i =1; i<=n; i++)  
77:    {  
78:      cin>>expected[i];  
79:    }  
80:    refreshPeg();  
81:    Move(1);  
82:    cout<<minSteps<<endl;  
83:    for(int i =1; i<=minSteps; i++)  
84:    {      
85:      cout<<minMoveSeq[i][0]<<" "<<minMoveSeq[i][1]<<endl;  
86:    }  
87:  }