2013年(34)
分类: C/C++
2013-05-01 15:53:00
比如字符串"1234"的输出为:
采用递归的思路,每一层递归的任务是输出当前string[begin, end]的每一个字母,在输出char a = string[begin]之后,对string[begin+1, end]进行递归调用。递归调用结束之后再输出string[begin, end]的第二个字母。然后对string[begin+2, end]进行递归调用。
例如"1234":
第一层递归遍历"1234",并且输出'1',之后对"234"进行递归。
第二层递归遍历"234", 这时候用首字母'2'代替在第一层递归中'1'后面的'/0',然后在'2'后面添加一个'/0',于是输出"12"。
第三层递归输出"123"
第四层递归输出"1234"。
然后退回到第三层递归。在将'4'添加到"123"后面被输出之后,本来依次输出'4'之后的元素,但是'4'已经是结尾,于是退回到第二层。
在第二层中,out之中已有"12",而且已经输出了"12"后的第一个元素'3',所以下一步是输出"12"后的第二个元素'4',所以下一个输出"124"。
以此类推。
其中还需要防止输出完全相同的的子串。如果是"1224",不能输出两次"124"(分别是第2个'2'和第3个'2')。所以在处理的时候需要判断之前是否已经出现过和当前元素一样的元素。如果有则说明当前元素的工作已经被之前同样的元素做了,不需要再做。这个判断的区间是[rec, i](i为当前元素下标, rec为本层递归需要被轮番代替的那个位置)。