最近在网上看到这样一个关于字符串的题目是这样的 :
假设有一个字符串aabcad,请写一段程序,去掉字符串中不相邻的重复字符串,即上述字符串处理之后的输出结果为:aabcd
同时也给出了答案,如下:
NSMutableString * str = [[NSMutableString alloc]initWithFormat:@"aabcad"];
for (int i = 0 ;i < str.length - 1 ;i++){
unsigned char a = [str characterAtIndex:i];
for (int j = i + 1 ;j < str.length ;j++){
unsigned char b = [str characterAtIndex:j];
if (a == b ){
if (j == i + 1){
}else{
[str deleteCharactersInRange:NSMakeRange(j, 1)];
}
}
}
}
NSLog(@"%@",str);
我感觉到这并不是我想要的答案,也可能是误解了出题者的意思,不管怎样,我对题目的理解是这样的,或许可以认为是另一道题,不要笑😁:
**假设有一个字符串aaaabbeffcfbfade,请写一段程序,去掉字符串中不相邻的重复字符串,即上述字符串处理之后的输出结果为:aaaabbffcd
如果按照上面的方法计算得到的结果是 aaabbeffcd,是有差别的。您看到这,不妨先停下来,不要往下看来,免得被我的思路干扰,自己尝试做一下,其实是很有趣的
弄了2、3个小时,终于写出了一个方法,感觉弄的有点复杂,还好弄出来了,放上代码😀😆,如有错误请指正,或者有简单方便的方法,欢迎指点;
- (NSString *)testWithStr:(NSString *)orignStr {
NSMutableString *str = [[NSMutableString alloc]initWithString:orignStr];
NSMutableArray *allStrArr = @[].mutableCopy;
NSMutableDictionary *allDic = @{}.mutableCopy;
for (int i = 0; i < str.length; i ++) {
NSString *eveyStr = [str substringWithRange:NSMakeRange(i, 1)];
[allStrArr addObject:eveyStr];
[allDic setObject:eveyStr forKey:@(i)];
}
NSMutableSet *strSet = [NSMutableSet setWithArray:allStrArr];
NSMutableIndexSet *indexset = [NSMutableIndexSet indexSet];
for (NSString *objStr in strSet) {
NSArray *sameValuKeyArr = [allDic allKeysForObject:objStr];
if (sameValuKeyArr.count > 1) {
for (NSNumber *keyNum in sameValuKeyArr) {
NSPredicate *predic = [NSPredicate predicateWithFormat:[NSString stringWithFormat:@"SELF BETWEEN {%d, %d}",[keyNum intValue] - 1, [keyNum intValue] + 1]];
NSArray *aaArr = [sameValuKeyArr filteredArrayUsingPredicate:predic];
if (aaArr.count == 1) {
[indexset addIndex:[keyNum intValue]];
}
}
}
}
NSMutableString *lastStr = @"".mutableCopy;
[allStrArr removeObjectsAtIndexes:indexset];
for (int i = 0; i < allStrArr.count; i ++) {
[lastStr appendString:allStrArr[i]];
}
NSLog(@"---===test0011---%@",lastStr);
return lastStr;
}
说一下大概的思路:
1.把字符串每个字符取出放在一个数组中;同时把每个字符作为value 和其对应的index作为可以放在一个字典中
2.把数组转化成NSSet,去掉数组中重复的元素,减少在后面的循环次数
3.根据set里面的元素,取出字典中该元素对应的key的集合(即字符串对应的index)。如果集合里面只有一个值,说明没有重复,不作处理;如果集合的值大于1,则判读每个key是否有相邻的伙伴,如果没有,则说明是分开的,符合条件,需要删除,就把该key放在IndexSet中;
4、原数组中删除IndexSet对应的value,然后重组字符串,就OK了
具体每一步分析如下:
- (NSString *)testWithStr:(NSString *)orignStr {
//例如 orignStr = @"aaaabbeffcfbfade";
NSMutableString *str = [[NSMutableString alloc]initWithString:orignStr];
NSMutableArray *allStrArr = @[].mutableCopy;//把字符串中每个字符分割成一个数组
NSMutableDictionary *allDic = @{}.mutableCopy;//把字符串中每个字符作为value,index 做为key 放入一个字典中
for (int i = 0; i < str.length; i ++) {
NSString *eveyStr = [str substringWithRange:NSMakeRange(i, 1)];//取出每个字符
[allStrArr addObject:eveyStr];//生成完整的数组 @["a", "a", "a", "a","b", "b"......]
[allDic setObject:eveyStr forKey:@(i)];//生成完整的字典 @{@1 : a, @2 :a, @3 : a, @4 : a, @5 : b.........}
}
NSMutableSet *strSet = [NSMutableSet setWithArray:allStrArr];// NSMutableSet 把数组中重复的字符都去掉 这样做在后面的操作中会减少循环次数 ["a", "b", "c", "d", ”e", "f"]
NSMutableIndexSet *indexset = [NSMutableIndexSet indexSet];//准备工作 最后数组中要删除的字符的index
for (NSString *objStr in strSet) {
NSArray *sameValuKeyArr = [allDic allKeysForObject:objStr];//从字典中取出具有相同value的key值,并放入一个集合 (取出每个a对应的key,每个 b...)
if (sameValuKeyArr.count > 1) {//大于1表示 这个字符有重复的需要做后续筛选 等于1则表述整个字符串中只有这一个字符不做处理
for (NSNumber *keyNum in sameValuKeyArr) {//取出这些相同的字符 对应的index
NSPredicate *predic = [NSPredicate predicateWithFormat:[NSString stringWithFormat:@"SELF BETWEEN {%d, %d}",[keyNum intValue] - 1, [keyNum intValue] + 1]];//正则表达式 取出数组中当前包括index在内的3个数(不确定有没有)
NSArray *aaArr = [sameValuKeyArr filteredArrayUsingPredicate:predic];
if (aaArr.count == 1) {//等于1则表示 该index 前后没有相邻的值, 是孤立的,符合条件 要被删除 把该index 放入 要删除的index集合中
[indexset addIndex:[keyNum intValue]];
}
}
}
}
//indexes: (6 10-13 15) 数组中 index 为6,10~13,15 这6个元素去掉
NSMutableString *lastStr = @"".mutableCopy;
[allStrArr removeObjectsAtIndexes:indexset];//数组中删除符合条件的元素
for (int i = 0; i < allStrArr.count; i ++) {
[lastStr appendString:allStrArr[i]];
}
NSLog(@"---===test0011---%@",lastStr);
return lastStr;
}
欢迎指正!