알고리즘 word break II

이 블 로 그 를 쓰 는 이 유 는 모든 결 과 를 출력 할 제목 입 니 다.
예 를 들 어 마이크로소프트 면접 100 문제 중 4 번 째 문제.
이원 트 리 에서 특정한 값 의 모든 경로 (트 리) 를 찾 습 니 다. 제목: 정수 와 이원 트 리 를 입력 하 십시오.나무의 뿌리 결점 부터 아래로 내 려 가서 잎 결점 이 지나 가 는 모든 결점 이 하나의 경 로 를 형성한다.입력 정수 와 같은 모든 경 로 를 출력 합 니 다.예 를 들 어 정수 22 와 아래 이원 수 10 / \ 5 12 / \ 4 7 을 입력 하면 두 가지 경 로 를 출력 합 니 다: 10, 12 와 10, 5, 7
그리고 leetcode 위 에 있 는 워드 브레이크 문제.
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"].
상기 문 제 는 모든 만족 조건 의 결 과 를 되 돌려 달라 고 요구 합 니 다. 그러면 우 리 는 우리 가 만난 모든 실행 가능 한 해 를 기억 하거나 기록 하면 서 출력 해 야 합 니 다.
먼저 마이크로소프트 의 면접 문 제 를 말 하고 모든 만족 조건 을 출력 하 는 경 로 를 요구한다.
나무 에 대해 우 리 는 모든 경로 가 뿌리 노드 에서 잎 노드 까지 라 는 것 을 알 고 있다. 그러면 중간 노드 를 지나 갈 때마다 우 리 는 sum - 현재 경로 의 값 을 기록 해 야 한다. 잎 노드 까지 우 리 는 현재 의 값 과 잎 노드 가 같 는 지 비교 해 야 한다. 만약 에 같다 면 우 리 는 합 법 적 인 경 로 를 얻 고 수출 하면 된다.
수출 후 에는 역 추적 문제 (DFS 와 유사) 에 직면 하 게 될 것 이다.
전체 코드 는 다음 과 같 습 니 다:

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>

using namespace std;

struct TreeNode{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x):val(x),left(NULL),right(NULL){};
};

void printPath(vector<int> & path)
{
//	cout << root->val << endl;
//	path.push_back(root->val);
	copy(path.begin(), path.end(), ostream_iterator<int>(cout, " "));
	cout << endl;
	return;
}
/*
 * treeSum      path         ，                。
 *         ，                          ，     ，
 *                    ，          ，         。
*/
void treeSum(TreeNode *root, int sum, vector<int> &path)
{
	
	if(root == NULL)return;
	if(root->left == NULL && root->right==NULL && root->val == sum)
		printPath(path);
	treeSum(root->left, sum-root->val, path);
	treeSum(root->right, sum-root->val, path);
	path.pop_back();//                 ，     ，  DFS
}


int main()
{
	TreeNode *node10 = new TreeNode(10);
	TreeNode *node5 = new TreeNode(5);
	TreeNode *node12 = new TreeNode(12);
	TreeNode *node4 = new TreeNode(4);
	TreeNode *node7 = new TreeNode(7);
	TreeNode *node6 = new TreeNode(6);
	node10->left = node5;
	node10->right = node12;
	node5->left = node4;
	node5->right = node7;
	//node12->left = node6;

	TreeNode *root= node10;
	int sum = 22;
	vector<int> path;
	treeSum(node10,sum, path);
	delete node10;
	delete node5;
	delete node12;
	delete node4;
	delete node7;
	delete node6;

	return 0;
}

leetcode 의 word break II 문제 에 대해
우선, 문자열 을 분리 할 수 있 는 지, 동적 계획 으로 해결 할 수 있 는 지 확인 합 니 다.
모든 실행 가능 한 해 를 출력 하려 면 비망록 을 사용 하여 모든 단계 의 전구 결점 을 기록 해 야 한다.(즉, 각 단어의 앞 단어의 위 치 를 기록 하 는 것 이다.)앞의 단어 가 유일 하지 않 을 수 있 기 때문에 가장 큰 개 수 는 n (총 n 개의 위치) 입 니 다.
주: i 의 위치 에 있어 s [0... i] 를 나 눌 수 있 는 지 여 부 를 판단 합 니 다. 만약 에 이 단어 자체 가 사전 에 있다 면 그의 전구 index 는 - 1 입 니 다. 만약 에 s [j.. i - 1] 가 합 법 적 인 단어 이 고 s [0...  j - 1] 도 합 법 적 인 단어 입 니 다. 그러면 그의 전구 index 는 j - 1 이 어야 합 니 다. 이런 식 으로 유추 하면 모든 위치의 전구 노드 의 개 수 는 n 입 니 다.
위 에서 - 1 이라는 음수 가 나 타 났 기 때문에 우 리 는 s 의 아래 표 시 를 1 부터 정의 합 니 다.즉, 다음 "i 번 째 문자" 는 s [i - 1] 를 나타 낸다.
따라서 2 차원 배열 비망록 prev [n + 1] [n] 을 정의 합 니 다. 그 중에서 prev [i] 는 제 i 문자 의 모든 전구 결점 을 나타 내 는 index 의 집합 입 니 다.

class Solution {

private:

    void backTrack(string s, vector<vector<int> > &prev, vector<string > &ret, string &path, int step)

    {

        if(step == 0) ret.push_back(path);

        if(prev[step].size())

        {

            for(int j = 0; j < prev[step].size(); ++j)

            {

                string temp = path;

                if(!path.empty()) path = ' ' + path;

                path = s.substr(prev[step][j], step - prev[step][j] ) + path;

                backTrack(s,prev,ret,path,prev[step][j]);

                path = temp;

            }

        }

    }

    

public:

    vector<string> wordBreak(string s, unordered_set<string> &dict) {

        vector<string> ret;

        if(s.empty()) return ret;

        int len = s.size();

        vector<vector< int > > prev(len+1,vector<int>());

        

        vector<bool > memo(len+1,false);

        memo[0] = true;

        for(int i = 1 ; i < len+1 ; ++i)

        {

            for(int j = 0; j < i; ++j)

            {

                if(memo[j] && dict.find(s.substr(j,i-j)) != dict.end())

                {

                    prev[i].push_back(j);

                    memo[i] = true;

                }

            }

        }

        string path;

        backTrack(s,prev,ret,path,len);

        return ret;

    }

};

이런 문제 에 대해 저 는 궁금 증 을 느 꼈 습 니 다. 재 귀 분석 에 익숙 하지 않 습 니 다. 이런 문 제 를 받 으 면 어떻게 해 야 할 지 모 르 겠 습 니 다. 지금 은 블 로 그 를 한 편 쓰 겠 습 니 다. 앞으로 많이 이해 해 주시 기 바 랍 니 다.삼가 이 글 을 당신 과 함께 격려 합 니 다.