[LintCode 702] Concatenated String with Uncommon Characters of Two Strings
Description
Two strings are given and you have to modify 1st string such that all the common characters of the 2nd strings have to be removed and the uncommon characters of the 2nd string have to be concatenated with uncommon characters of the 1st string.
给出两个字符串, 你需要修改第一个字符串，将所有与第二个字符串中相同的字符删除, 并且第二个字符串中不同的字符与第一个字符串的不同字符连接
Example:
Example 1:
Input : s1 = "aacdb", s2 = "gafd"
Output : "cbgf"
Example 2:
Input : s1 = "abcs", s2 = "cxzca"
Output : "bsxz"
Note
这道题有两个地方开始犯了错：
1. 从S1中删除重复元素时，我一开始使用了for循环 for i in range(0, len(s1)):，而此时 s1剔除元素的时候长度是动态减少的，而for循环的迭代器已经生成会一直执行到原有长度的index，就会造成溢出。所以需要换成while执行避免这个问题
2. 同样的问题也是出在删除元素的时候，此时扫描到的元素位置经过删除后，之后的位置都会前移一位，所以扫描位置不需要向前。
Update Review
可以修改i的值，但每次循环之后for语句又会重新对i赋值，所以你问的问题不在于能否修改i，而是修改迭代器的行为，答案是不能。
你可以用while，或者，用个生成器：
def incSeq(seq):
start = 0
for i in xrange(1, len(seq)):
if seq[i] < seq[i-1]:
yield start, i - start
start = i
maxIncSeq = reduce(lambda x,y: x if x[1]>y[1] else y, incSeq(seq))
得到最长递增子串长度及起始位置，时间复杂度O(n).
以上是关于使用for 和 while时的一些区别。
Code
Python3 on LintCode
class Solution:
"""
@param s1: the 1st string
@param s2: the 2nd string
@return: uncommon characters of given strings
"""
def concatenetedString(self, s1, s2):
# write your code here
set1 = set(s1)
set2 = set(s2)
join_set = set1 & set2
print(join_set)
i = 0
while i < len(s1):
# for i in range(0, len(s1)):
if s1[i] in join_set:
s1 = s1[0:i]+s1[i+1:]
# !!!index has changed here
i -= 1
i += 1
for j in range(0, len(s2)):
if s2[j] not in join_set:
s1 += s2[j]
return s1
Ref Code
本参考程序来自九章算法，由 @令狐冲 提供
直接讲交集和提取合并在一起写，代码更简单，不过和自己的思路基本类似
class Solution:
"""
@param s1: the 1st string
@param s2: the 2nd string
@return: uncommon characters of given strings
"""
def concatenetedString(self, s1, s2):
# write your code here
ans = []
for c in s1:
if c not in s2:
ans.append(c)
for c in s2:
if c not in s1:
ans.append(c)
return "".join(ans)
This blog is under a CC BY-NC-SA 3.0 Unported License
本文使用 CC BY-NC-SA 3.0 中国 协议许可
署名-非商业性使用-相同方式共享（BY-NC-SA）：使用者可以对本创作进行共享、演绎，但使用时须进行署名（同时标明是否（对原始作品）作了修改），且不得运用于商业目的，采用本创作的内容必须同样采用本协议进行授权。详情请参考协议细则。
本文链接：https://dataleoz.com/lintcode-Concatenated-String-with-Uncommon-Characters-of-Two-Strings/