iOS关于“去掉字符串中不相邻的重复字符串”的算法

最近在网上看到这样一个关于字符串的题目是这样的 :

假设有一个字符串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;
}

欢迎指正!

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容