Update README.md

neycyanshi · web-flow · commit e4a41e82c35a · 2017-02-07T23:30:29.000+08:00
递归交换str[begin]和str[i]时，判断是否在此i前已经交换过重复的字符str[i]。
diff --git a/028-字符串的排列/README.md b/028-字符串的排列/README.md
@@ -200,20 +200,26 @@ public:
                 i++)
             {
                 //debug <<str[i] <<str[begin] <<endl;
-                if(i == begin || str[i] != str[begin])
+                if(!HasDuplicate(str, begin, i))
                 {
-
                     swap(str[i], str[begin]);
-
+                    debug <<"swap " <<str[i] <<"(" <<i <<")" <<" and " <<str[begin] <<"(" <<begin <<")" <<endl;
                     PermutationRecursion(str, begin + 1);
-
+                    //copy(str.begin( ), str.degin( ) + i, ostream_iterator<char>(cout," "));
                     swap(str[i], str[begin]);
-
                 }
             }
         }
     }
-
+    
+private:
+    //find duplicate of str[i] in str[k,i)
+    bool HasDuplicate(string& str, int k, int i) const {
+		for (int p = k; p < i; p++)
+			if (str[p] == str[i]) return true;
+
+		return false;
+	}
 };
 
 int __tmain( )

Original file line number	Diff line number	Diff line change
`@@ -200,20 +200,26 @@ public:`
`200`	`200`	`i++)`
`201`	`201`	`{`
`202`	`202`	`//debug <<str[i] <<str[begin] <<endl;`
`203`		`- if(i == begin \|\| str[i] != str[begin])`
	`203`	`+ if(!HasDuplicate(str, begin, i))`
`204`	`204`	`{`
`205`		`-`
`206`	`205`	`swap(str[i], str[begin]);`
`207`		`-`
	`206`	`+ debug <<"swap " <<str[i] <<"(" <<i <<")" <<" and " <<str[begin] <<"(" <<begin <<")" <<endl;`
`208`	`207`	`PermutationRecursion(str, begin + 1);`
`209`		`-`
	`208`	`+ //copy(str.begin( ), str.degin( ) + i, ostream_iterator<char>(cout," "));`
`210`	`209`	`swap(str[i], str[begin]);`
`211`		`-`
`212`	`210`	`}`
`213`	`211`	`}`
`214`	`212`	`}`
`215`	`213`	`}`
`216`		`-`
	`214`	`+`
	`215`	`+private:`
	`216`	`+ //find duplicate of str[i] in str[k,i)`
	`217`	`+ bool HasDuplicate(string& str, int k, int i) const {`
	`218`	`+ for (int p = k; p < i; p++)`
	`219`	`+ if (str[p] == str[i]) return true;`
	`220`	`+`
	`221`	`+ return false;`
	`222`	`+ }`
`217`	`223`	`};`
`218`	`224`
`219`	`225`	`int __tmain( )`