0votos

Longitud de la substring con los caracteres dados en Haskell

por josejuan hace 6 años

Ésta no es eficiente (cuadrática en la longitud de S), pero creo que elegante. De todos modos, se me ocurre un algoritmo con coste O(|S| |C|) o menor.

Dada una String s y unos caracteres desarrollar el código que determine la longitud de la substring más corta de s que contenga todos los caracteres dados.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import qualified Data.Set as S 
import Data.List 
 
minSubSet :: Ord a => S.Set a -> [a] -> [a] 
minSubSet cs = 
  head .                                  -- La primer cadena... 
  sortBy ((.length).compare.length) .     -- ...ordenando por longitud... 
  filter (S.isSubsetOf cs . S.fromList) . -- ...de las que contienen todos los elementos... 
  concatMap tails . inits                 -- ...de todas las subcadenas. 
 
{-- 
 
  *Main> minSubSet (S.fromList "ELO") "ELRAPIDOLINCESECOMIOALRATON" 
  "OLINCE" 
 
--} 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.