LeetCode練習-文字列

一、palindrome-partitioning
タイトルはGiven a string s,partition s such that every substring of the partition is a palindrome.Return all possible palindrome partitioning of s. For example, given s ="aab", Return   [     ["aa","b"],     ["a","a","b"]   ]
考え方:ダイナミックプランニング+深度優先ループ(DFS)
1、動的規範アルゴリズムで分子回文列を作成する
2、DFSで可能な場合を遍歴する
コード:

class Solution {
public:
    vector > partition(string s){
        vector > result;
        vector array;
        if(s.length()==0)
            return result;
        vector > flag = dp(s);

        dfs(s, 0, flag, array, result);
        return result;
    }

    void dfs(string s, int begin, vector > flag, vector array, vector > &result) {  
        if(begin==s.length()) {
            result.push_back(array); 
            //array.clear();
            return;  
        }  

        for(int i=begin;i temp(array);
                temp.push_back(s.substr(begin,i+1-begin));
                //cout << "begin=" << begin << "; i+1=" << (i+1) << endl;
                //cout << array.back() << endl;
                dfs(s, i+1, flag, temp, result);  
            }  
        }  
    }
    vector > dp(string s){
        int len = s.length();
        vector > flag(len, vector(len, 0));
        int i, j;
        for(i=len-1; i>=0; --i){
            for(j=i; j

ローカルテストコード:

vector > dp(string s);//    ，    
void dfs(string s, int begin, vector > flag, vector array, vector > &result);//      
vector > partition(string s);
int main(){
	string s = "abcbad";
	//cout << s.substr(1, 2) << endl;

	vector > flag = dp(s);
	int i, j;
	for(i=0; i > result;
	//vector array;
	//dfs(s, 0, flag, array, result);
	vector > result = partition(s);
	
	for(i=0; i

二、add-binary
タイトルはGiven two binary strings,return their sum(also a binary string).For example, a ="11"b ="1"Return"100"
コード:

class Solution {
public:
    string addBinary(string a, string b) {
        string sum;//  
        int up=0;//  
        int i=a.length()-1;
        int j=b.length()-1;
        while(i>=0 && j>=0){
            int temp = a[i]+b[j]-'0'-'0' + up;//         
            if(temp == 3){
                up = 1;
                sum.insert(sum.begin(), '1');
            }
            else if(temp == 2){
                up = 1;
                sum.insert(sum.begin(), '0');
            }
            else if(temp == 1){
                up = 0;
                sum.insert(sum.begin(), '1');
            }
            else if(temp == 0){
                up = 0;
                sum.insert(sum.begin(), '0');
            }
            --i;
            --j;
        }

        while(i>=0){//    i>=0，  a ， a         
            int temp = a[i] - '0' +up; 
            if(temp == 2){
                up = 1;
                sum.insert(sum.begin(), '0');
            }
            else if(temp == 1){
                up = 0;
                sum.insert(sum.begin(), '1');
            }
            else if(temp == 0){
                up = 0;
                sum.insert(sum.begin(), '0');
            }
            --i;
        }	
        while(j>=0){//    j>=0，  b ， b         
            int temp = b[j] - '0' + up;
            if(temp == 2){
                up = 1;
                sum.insert(sum.begin(), '0');
            }
            else if(temp == 1){
                up = 0;
                sum.insert(sum.begin(), '1');
            }
            else if(temp == 0){
                up = 0;
                sum.insert(sum.begin(), '0');
            }
            --j;
        }
        if(up == 1)//          
            sum.insert(sum.begin(), '1');
        return sum;
    }
};

ローカルテストコード:

int main(){
	string a;
	string b;
	
	cout << "a: ";
	getline(cin, a);
	cout << "b: ";
	getline(cin, b);
	
	string s = addBinary(a, b);
	//string s = "ss";
	cout << s << endl;
	return 0;
}