从方案中的字符串中删除重复的字符

Question

我一直在尝试这个问题很长一段时间，但没有得到很大的回应。问题是要求产生一个字符串，其中来自输入字符串的所有重复字符被字符的单个实例替换。

例如，

(remove-repeats "aaaab") => "ab" 
(remove-repeats "caaabb aa") => "cab a" 

因为我试图做到这一点使用递归累计，所以到目前为止，我有：

(define (remove-repeats s) 
    (local 
    [(define (remove-repeats-acc s1 removed-so-far) 
     (cond 
     [(empty? (string->list s1))""] 
     [else 
     (cond 
      [(equal? (first (string->list s1)) (second (string->list s1))) 
     (list->string (remove-repeats-acc (remove (second (string->list s1)) (string->list s1)) (add1 removed-so-far)))] 
      [else (list->string (remove-repeats-acc (rest (string->list s1)) removed-so-far))])]))] 
    (remove-repeats-acc s 0))) 

但这似乎并不正确。请帮我修改这个工作。

谢谢！

Answer 1

字符串有点让人讨厌，所以我们将它包装在一个处理列表的工作函数中。通过这种方式，我们可以避免随处转换。

(define (remove-repeats str) 
    (list->string (remove-repeats/list (string->list str)))) 

现在我们可以用一个简单的递归定义删除，重复/列表功能：

(define (remove-repeats/list xs) 
    (cond 
    [(empty? xs) xs] 
    [(empty? (cdr xs)) xs] 
    [(equal? (car xs) (cadr xs)) (remove-repeats/list (cdr xs))] 
    [else (cons (car xs) (remove-repeats/list (cdr xs)))])) 

这不是尾递归，但现在它应该是更容易添加蓄电池：

(define (remove-repeats str) 
    (list->string (remove-repeats/list-acc (string->list str) '()))) 

(define (remove-repeats/list-acc xs acc) 
    (cond 
    [(empty? xs) (reverse acc)] 
    [(empty? (cdr xs)) (reverse (cons (car xs) acc))] 
    [(equal? (car xs) (cadr xs)) (remove-repeats/list-acc (cdr xs) acc)] 
    [else (remove-repeats/list-acc (cdr xs) (cons (car xs) acc))])) 

Answer 2

这里有一个版本，我喜欢的，在Typed Racket：

#lang typed/racket 
(: remove-repeats : String -> String) 
(define (remove-repeats s) 
    (define-values (chars last) 
    (for/fold: ([chars : (Listof Char) null] [last : (Option Char) #f]) 
     ([c (in-string s)] #:when (not (eqv? last c))) 
     (values (cons c chars) c))) 
    (list->string (reverse chars)))