ultimo - split javascript ejemplo
Encuentra la subcadena de inicio común más larga en un conjunto de cadenas (30)
Este es un desafío para encontrar el JavaScript más elegante, Ruby u otra solución para un problema relativamente trivial.
Este problema es un caso más específico del problema de la subcadena común más larga . Necesito encontrar solo la subcadena de inicio común más larga en una matriz. Esto simplifica enormemente el problema.
Por ejemplo, la subcadena más larga en [interspecies, interstelar, interstate] es "inters". Sin embargo, no necesito encontrar "ific" en [specifics, terrific] .
He resuelto el problema al codificar rápidamente una solución en JavaScript como parte de mi respuesta sobre la finalización de pestañas en forma de shell ( página de prueba aquí ). Aquí está esa solución, ligeramente retocada:
function common_substring(data) {
var i, ch, memo, idx = 0
do {
memo = null
for (i=0; i < data.length; i++) {
ch = data[i].charAt(idx)
if (!ch) break
if (!memo) memo = ch
else if (ch != memo) break
}
} while (i == data.length && idx < data.length && ++idx)
return (data[0] || '''').slice(0, idx)
}
Este código está disponible en este Gist junto con una solución similar en Ruby. Puede clonar la esencia como un repositorio git para probarlo:
$ git clone git://gist.github.com/257891.git substring-challenge
No estoy muy contento con esas soluciones. Tengo la sensación de que podrían ser resueltos con más elegancia y menos complejidad de ejecución, por eso estoy publicando este desafío.
Voy a aceptar como respuesta la solución que encuentro más elegante o concisa. Aquí está, por ejemplo, un loco hack de Ruby que se me ocurre: definir el operador & en String:
# works with Ruby 1.8.7 and above
class String
def &(other)
difference = other.to_str.each_char.with_index.find { |ch, idx|
self[idx].nil? or ch != self[idx].chr
}
difference ? self[0, difference.last] : self
end
end
class Array
def common_substring
self.inject(nil) { |memo, str| memo.nil? ? str : memo & str }.to_s
end
end
Se prefieren las soluciones en JavaScript o Ruby, pero puede mostrar una solución inteligente en otros idiomas siempre que explique lo que está sucediendo. Solo código de la biblioteca estándar, por favor.
Actualización: mis soluciones favoritas
kennebec solución de clasificación de JavaScript de kennebec como la "respuesta" porque me pareció inesperado y genial. Si no tomamos en cuenta la complejidad de la clasificación real (imaginemos que está infinitamente optimizada por la implementación del lenguaje), la complejidad de la solución es simplemente comparar dos cadenas.
Otras excelentes soluciones:
- La "avaricia regex" de FM toma uno o dos minutos para captar, pero luego la elegancia te golpea. Yehuda Katz también creó una solución de expresiones regulares , pero es más compleja
-
commonprefixen Python - Roberto Bonvallet usó una característica hecha para manejar las rutas del sistema de archivos para resolver este problema - Haskell one-liner es corto como si estuviera comprimido y es hermoso
- el sencillo de un solo trazador de líneas de Ruby
¡Gracias por participar! Como puede ver en los comentarios, aprendí mucho (incluso sobre Ruby).
A menudo es más elegante usar una biblioteca madura de código abierto en lugar de utilizar la tuya propia. Luego, si no se ajusta completamente a sus necesidades, puede ampliarlo o modificarlo para mejorarlo y dejar que la comunidad decida si pertenece a la biblioteca.
diff-lcs es una buena gema Ruby para la subcadena menos común.
Al darse cuenta del riesgo de que esto se convierta en una combinación de código de golf (¿o es esa la intención?), Aquí está mi solución usando sed , copiada de mi respuesta a otra pregunta SO y acortada a 36 caracteres (30 de los cuales son la expresión sed real) . Espera que las cadenas (cada una en una línea separada) se suministren en una entrada estándar o en archivos pasados como argumentos adicionales.
sed ''N;s/^/(.*/).*/n/1.*$//1/n/1/;D''
Un script con sed en la línea shebang pesa 45 caracteres:
#!/bin/sed -f
N;s/^/(.*/).*/n/1.*$//1/n/1/;D
Una ejecución de prueba del script (llamado longestprefix ), con cadenas suministradas como un "documento aquí":
$ ./longestprefix <<EOF
> interspecies
> interstelar
> interstate
> EOF
inters
$
Aquí hay una solución eficiente en ruby. Basé la idea de la estrategia para un juego de adivinar hi / lo en el que cero iterativamente en el prefijo más largo.
Alguien me corrige si me equivoco, pero creo que la complejidad es O (n log n), donde n es la longitud de la cadena más corta y el número de cadenas se considera una constante.
def common(strings)
lo = 0
hi = strings.map(&:length).min - 1
return '''' if hi < lo
guess, last_guess = lo, hi
while guess != last_guess
last_guess = guess
guess = lo + ((hi - lo) / 2.0).ceil
if strings.map { |s| s[0..guess] }.uniq.length == 1
lo = guess
else
hi = guess
end
end
strings.map { |s| s[0...guess] }.uniq.length == 1 ? strings.first[0...guess] : ''''
end
Y algunos controles que funciona:
>> common %w{ interspecies interstelar interstate }
=> "inters"
>> common %w{ dog dalmation }
=> "d"
>> common %w{ asdf qwerty }
=> ""
>> common ['''', ''asdf'']
=> ""
Aquí hay una solución que usa expresiones regulares en Ruby:
def build_regex(string)
arr = []
arr << string.dup while string.chop!
Regexp.new("^(#{arr.join("|")})")
end
def substring(first, *strings)
strings.inject(first) do |accum, string|
build_regex(accum).match(string)[0]
end
end
Combinando respuestas de Kennebec , Florian F y jberryman se obtiene el siguiente Haskell one-liner:
commonPrefix l = map fst . takeWhile (uncurry (==)) $ zip (minimum l) (maximum l)
Con Control.Arrow uno puede obtener una forma libre de puntos:
commonPrefix = map fst . takeWhile (uncurry (==)) . uncurry zip . (minimum &&& maximum)
En Python no usaría nada más que la función de commonprefix existente que mostré en otra respuesta, pero no pude evitar reinventar la rueda :P Este es mi enfoque basado en iteradores:
>>> a = ''interspecies interstelar interstate''.split()
>>>
>>> from itertools import takewhile, chain, izip as zip, imap as map
>>> ''''.join(chain(*takewhile(lambda s: len(s) == 1, map(set, zip(*a)))))
''inters''
Editar: Explicación de cómo funciona esto.
zip genera tuplas de elementos tomando uno de cada elemento de a la vez:
In [6]: list(zip(*a)) # here I use list() to expand the iterator
Out[6]:
[(''i'', ''i'', ''i''),
(''n'', ''n'', ''n''),
(''t'', ''t'', ''t''),
(''e'', ''e'', ''e''),
(''r'', ''r'', ''r''),
(''s'', ''s'', ''s''),
(''p'', ''t'', ''t''),
(''e'', ''e'', ''a''),
(''c'', ''l'', ''t''),
(''i'', ''a'', ''e'')]
Al asignar un set estos elementos, obtengo una serie de letras únicas:
In [7]: list(map(set, _)) # _ means the result of the last statement above
Out[7]:
[set([''i'']),
set([''n'']),
set([''t'']),
set([''e'']),
set([''r'']),
set([''s'']),
set([''p'', ''t'']),
set([''a'', ''e'']),
set([''c'', ''l'', ''t'']),
set([''a'', ''e'', ''i''])]
takewhile(predicate, items) toma elementos de esto mientras que el predicado es True; en este caso particular, cuando el set tiene un elemento, es decir, todas las palabras tienen la misma letra en esa posición:
In [8]: list(takewhile(lambda s: len(s) == 1, _))
Out[8]:
[set([''i'']),
set([''n'']),
set([''t'']),
set([''e'']),
set([''r'']),
set([''s''])]
En este punto tenemos una serie de conjuntos, cada uno con una letra del prefijo que estábamos buscando. Para construir la cadena, los chain en un solo iterable, del cual obtenemos las letras para join a la cadena final.
La magia de usar iteradores es que todos los elementos se generan a demanda, por lo que cuando se takewhile deja de pedir elementos, el ajuste se detiene en ese punto y no se realiza ningún trabajo innecesario. Cada llamada de función en mi one-liner tiene un implícito for y un break implícito.
En Python:
>>> from os.path import commonprefix
>>> commonprefix(''interspecies interstelar interstate''.split())
''inters''
En lugar de ordenar, podrías obtener el mínimo y el máximo de las cadenas.
Para mí, la elegancia en un programa de computadora es un equilibrio de velocidad y simplicidad. No debería hacer un cálculo innecesario, y debería ser lo suficientemente simple para hacer que su corrección sea evidente.
Podría llamar a la solución de clasificación "inteligente", pero no "elegante".
Es una cuestión de gusto, pero esta es una versión de javascript simple: ordena la matriz y luego mira solo los primeros y últimos elementos.
// la subcadena de inicio común más larga en una matriz
function sharedStart(array){
var A= array.concat().sort(),
a1= A[0], a2= A[A.length-1], L= a1.length, i= 0;
while(i<L && a1.charAt(i)=== a2.charAt(i)) i++;
return a1.substring(0, i);
}
POBLACIÓN
sharedStart([''interspecies'', ''interstelar'', ''interstate'']) //=> ''inters''
sharedStart([''throne'', ''throne'']) //=> ''throne''
sharedStart([''throne'', ''dungeon'']) //=> ''''
sharedStart([''cheese'']) //=> ''cheese''
sharedStart([]) //=> ''''
sharedStart([''prefix'', ''suffix'']) //=> ''''
Esta es muy similar a la solución de Roberto Bonvallet, excepto en ruby.
chars = %w[interspecies interstelar interstate].map {|w| w.split('''') }
chars[0].zip(*chars[1..-1]).map { |c| c.uniq }.take_while { |c| c.size == 1 }.join
La primera línea reemplaza cada palabra con una matriz de caracteres. A continuación, uso zip para crear esta estructura de datos:
[["i", "i", "i"], ["n", "n", "n"], ["t", "t", "t"], ...
map y uniq reducen esto a [["i"],["n"],["t"], ...
take_while saca los caracteres del conjunto hasta que encuentra uno donde el tamaño no es uno (lo que significa que no todos los caracteres son iguales). Finalmente, los vuelvo a join .
Esto de ninguna manera es elegante, pero si quieres conciso:
Ruby, 71 caracteres
def f(a)b=a[0];b[0,(0..b.size).find{|n|a.any?{|i|i[0,n]!=b[0,n]}}-1]end
Si quieres que se desenrolle, se ve así:
def f(words)
first_word = words[0];
first_word[0, (0..(first_word.size)).find { |num_chars|
words.any? { |word| word[0, num_chars] != first_word[0, num_chars] }
} - 1]
end
Fun solución Ruby alternativa:
def common_prefix(*strings)
chars = strings.map(&:chars)
length = chars.first.zip( *chars[1..-1] ).index{ |a| a.uniq.length>1 }
strings.first[0,length]
end
p common_prefix( ''foon'', ''foost'', ''forlorn'' ) #=> "fo"
p common_prefix( ''foost'', ''foobar'', ''foon'' ) #=> "foo"
p common_prefix( ''a'',''b'' ) #=> ""
Podría ayudar a acelerar si usó chars = strings.sort_by(&:length).map(&:chars) , ya que cuanto más corta sea la primera cadena, más cortas serán las matrices creadas por zip . Sin embargo, si te preocupa la velocidad, probablemente no deberías usar esta solución de ninguna manera. :)
Golfed JS solución solo por diversión:
w=["hello", "hell", "helen"];
c=w.reduce(function(p,c){
for(r="",i=0;p[i]==c[i];r+=p[i],i++){}
return r;
});
Javascript clona la excelente respuesta de AShelly .
Requiere Array#reduce que solo es compatible con Firefox.
var strings = ["interspecies", "intermediate", "interrogation"]
var sub = strings.reduce(function(l,r) {
while(l!=r.slice(0,l.length)) {
l = l.slice(0, -1);
}
return l;
});
La solución aceptada está quebrada (por ejemplo, devuelve a para cadenas como [''a'', ''ba''] ). La solución es muy simple, literalmente tiene que cambiar solo 3 caracteres (de indexOf(tem1) == -1 a indexOf(tem1) != 0 ) y la función funcionaría como se esperaba.
Desafortunadamente, cuando intenté editar la respuesta para corregir el error tipográfico, SO me dijo que "las ediciones deben tener al menos 6 caracteres". Podría cambiar más que esos 3 caracteres, mejorando la nomenclatura y la legibilidad, pero eso parece un poco demasiado.
Por lo tanto, a continuación se muestra una versión fija y mejorada (al menos desde mi punto de vista) de la solución de Kennebec:
function commonPrefix(words) {
max_word = words.reduce(function(a, b) { return a > b ? a : b });
prefix = words.reduce(function(a, b) { return a > b ? b : a }); // min word
while(max_word.indexOf(prefix) != 0) {
prefix = prefix.slice(0, -1);
}
return prefix;
}
(en jsFiddle )
Tenga en cuenta que utiliza el método de reduce (JavaScript 1.8) para encontrar máximos / mínimos alfanuméricos en lugar de ordenar la matriz y luego buscar los primeros y los últimos elementos de la misma.
Mi Haskell de una sola línea:
import Data.List
commonPre :: [String] -> String
commonPre = map head . takeWhile (/(x:xs)-> all (==x) xs) . transpose
EDITAR: barkmadley dio una buena explicación del código a continuación. También agregaría que haskell usa la evaluación perezosa, por lo que podemos ser perezosos con respecto al uso que hacemos de la transpose ; solo transpondrá nuestras listas tanto como sea necesario para encontrar el final del prefijo común.
Mi solución de Javascript :
IMOP, utilizar el género es demasiado complicado. Mi solución es comparar letra por letra mediante el bucle de la matriz. Devuelve la cadena si la letra no está escrita.
Esta es mi solución:
var longestCommonPrefix = function(strs){
if(strs.length < 1){
return '''';
}
var p = 0, i = 0, c = strs[0][0];
while(p < strs[i].length && strs[i][p] === c){
i++;
if(i === strs.length){
i = 0;
p++;
c = strs[0][p];
}
}
return strs[0].substr(0, p);
};
Mi solución en Java:
public static String compute(Collection<String> strings) {
if(strings.isEmpty()) return "";
Set<Character> v = new HashSet<Character>();
int i = 0;
try {
while(true) {
for(String s : strings) v.add(s.charAt(i));
if(v.size() > 1) break;
v.clear();
i++;
}
} catch(StringIndexOutOfBoundsException ex) {}
return strings.iterator().next().substring(0, i);
}
Mientras leía estas respuestas con toda la programación funcional de lujo, clasificación y expresiones regulares y otras cosas, solo pensé: ¿qué tiene de malo un poco de C? Así que aquí hay un pequeño programa de aspecto tonto.
#include <stdio.h>
int main (int argc, char *argv[])
{
int i = -1, j, c;
if (argc < 2)
return 1;
while (c = argv[1][++i])
for (j = 2; j < argc; j++)
if (argv[j][i] != c)
goto out;
out:
printf("Longest common prefix: %.*s/n", i, argv[1]);
}
Compílalo, ejecútalo con tu lista de cadenas como argumentos de la línea de comando, ¡y luego véndeme para usar goto !
No es código de golf, pero pediste algo elegante, y tiendo a pensar que la recursividad es divertida. Java.
/** Recursively find the common prefix. */
public String findCommonPrefix(String[] strings) {
int minLength = findMinLength(strings);
if (isFirstCharacterSame(strings)) {
return strings[0].charAt(0) + findCommonPrefix(removeFirstCharacter(strings));
} else {
return "";
}
}
/** Get the minimum length of a string in strings[]. */
private int findMinLength(final String[] strings) {
int length = strings[0].size();
for (String string : strings) {
if (string.size() < length) {
length = string.size();
}
}
return length;
}
/** Compare the first character of all strings. */
private boolean isFirstCharacterSame(String[] strings) {
char c = string[0].charAt(0);
for (String string : strings) {
if (c != string.charAt(0)) return false;
}
return true;
}
/** Remove the first character of each string in the array,
and return a new array with the results. */
private String[] removeFirstCharacter(String[] source) {
String[] result = new String[source.length];
for (int i=0; i<result.length; i++) {
result[i] = source[i].substring(1);
}
return result;
}
No parece tan complicado si no está demasiado preocupado por el rendimiento final:
def common_substring(data)
data.inject { |m, s| s[0,(0..m.length).find { |i| m[i] != s[i] }.to_i] }
end
Una de las características útiles de Inject es la posibilidad de preiniciar con el primer elemento de la matriz que se está procesando. Esto evita la verificación nim memo.
puts common_substring(%w[ interspecies interstelar interstate ]).inspect
# => "inters"
puts common_substring(%w[ feet feel feeble ]).inspect
# => "fee"
puts common_substring(%w[ fine firkin fail ]).inspect
# => "f"
puts common_substring(%w[ alpha bravo charlie ]).inspect
# => ""
puts common_substring(%w[ fork ]).inspect
# => "fork"
puts common_substring(%w[ fork forks ]).inspect
# => "fork"
Actualización: si el golf es el juego aquí, entonces 67 caracteres:
def f(d)d.inject{|m,s|s[0,(0..m.size).find{|i|m[i]!=s[i]}.to_i]}end
Otra forma de hacerlo: use la codicia de expresiones regulares.
words = %w(interspecies interstelar interstate)
j = ''=''
str = ['''', *words].join(j)
re = "[^#{j}]*"
str =~ //A
(?: #{j} ( #{re} ) #{re} )
(?: #{j} /1 #{re} )*
/z/x
p $1
Y el one-liner, cortesía de mislav (50 caracteres):
p ARGV.join('' '').match(/^(/w*)/w*(?: /1/w*)*$/)[1]
Probablemente esta no sea la solución más concisa (depende si ya tienes una biblioteca para esto), pero un método elegante es usar un trie. Utilizo intentos para implementar la finalización de pestañas en mi intérprete Scheme:
http://github.com/jcoglan/heist/blob/master/lib/trie.rb
Por ejemplo:
tree = Trie.new
%w[interspecies interstelar interstate].each { |s| tree[s] = true }
tree.longest_prefix('''')
#=> "inters"
También los uso para emparejar nombres de canales con comodines para el protocolo de Bayeux; ver estos:
http://github.com/jcoglan/faye/blob/master/client/channel.js
http://github.com/jcoglan/faye/blob/master/lib/faye/channel.rb
Ruby one-liner:
l=strings.inject{|l,s| l=l.chop while l!=s[0...l.length];l}
Solo necesita recorrer todas las cadenas hasta que difieran, luego lleve la subcadena hasta este punto.
Pseudocódigo:
loop for i upfrom 0
while all strings[i] are equal
finally return substring[0..i]
Common Lisp:
(defun longest-common-starting-substring (&rest strings)
(loop for i from 0 below (apply #''min (mapcar #''length strings))
while (apply #''char=
(mapcar (lambda (string) (aref string i))
strings))
finally (return (subseq (first strings) 0 i))))
Solo por diversión, aquí hay una versión escrita en (SWI-) PROLOG:
common_pre([[C|Cs]|Ss], [C|Res]) :-
maplist(head_tail(C), [[C|Cs]|Ss], RemSs), !,
common_pre(RemSs, Res).
common_pre(_, []).
head_tail(H, [H|T], T).
Corriendo:
?- S=["interspecies", "interstelar", "interstate"], common_pre(S, CP), string_to_list(CPString, CP).
Da:
CP = [105, 110, 116, 101, 114, 115],
CPString = "inters".
Explicación:
(SWI-) PROLOG trata cadenas como listas de códigos de caracteres (números). Todo el predicado common_pre/2 does es coincidencia de patrón recursiva para seleccionar el primer código ( C ) del encabezado de la primera lista (cadena, [C|Cs] ) en la lista de todas las listas (todas las cadenas, [[C|Cs]|Ss] ), y agrega el código coincidente C al resultado si es común para todos los encabezados (restantes) de todas las listas (cadenas), de lo contrario termina.
Agradable, limpio, simple y eficiente ... :)
Una versión de JavaScript basada en el algoritmo de @Svante :
function commonSubstring(words){
var iChar, iWord,
refWord = words[0],
lRefWord = refWord.length,
lWords = words.length;
for (iChar = 0; iChar < lRefWord; iChar += 1) {
for (iWord = 1; iWord < lWords; iWord += 1) {
if (refWord[iChar] !== words[iWord][iChar]) {
return refWord.substring(0, iChar);
}
}
}
return refWord;
}
Una versión de ruby basada en el algoritmo de @Svante. Corre ~ 3 veces más rápido que mi primera.
def common_prefix set
i=0
rest=set[1..-1]
set[0].each_byte{|c|
rest.each{|e|return set[0][0...i] if e[i]!=c}
i+=1
}
set
end
Yo haría lo siguiente:
- Tome la primera cadena de la matriz como la subcadena de partida inicial.
- Tome la siguiente cadena de la matriz y compare los caracteres hasta que se llegue al final de una de las cadenas o se encuentre una discrepancia. Si se encuentra una discrepancia, reduzca la subcadena de inicio a la longitud donde se encontró la falta de coincidencia.
- Repita el paso 2 hasta que todas las cadenas hayan sido probadas.
Aquí hay una implementación de JavaScript:
var array = ["interspecies", "interstelar", "interstate"],
prefix = array[0],
len = prefix.length;
for (i=1; i<array.length; i++) {
for (j=0, len=Math.min(len,array[j].length); j<len; j++) {
if (prefix[j] != array[i][j]) {
len = j;
prefix = prefix.substr(0, len);
break;
}
}
}
Python 2.6 (r26:66714, Oct 4 2008, 02:48:43)
>>> a = [''interspecies'', ''interstelar'', ''interstate'']
>>> print a[0][:max(
[i for i in range(min(map(len, a)))
if len(set(map(lambda e: e[i], a))) == 1]
) + 1]
inters
i for i in range(min(map(len, a))), el número de búsquedas máximas no puede ser mayor que la longitud de la cadena más corta; en este ejemplo esto evaluaría a[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]len(set(map(lambda e: e[i], a))), 1) crea una matriz del carácteri-thpara cada cadena en la lista; 2) hacer un juego de eso; 3) determinar el tamaño del conjunto[i for i in range(min(map(len, a))) if len(set(map(lambda e: e[i], a))) == 1], incluya solo los caracteres, para los cuales el tamaño del conjunto es 1 (todos los personajes en esa posición eran iguales ...); aquí evaluaría a[0, 1, 2, 3, 4, 5]finalmente tome el
max, agregue uno, y obtenga la subcadena ...
Nota: lo anterior no funciona para a = [''intersyate'', ''intersxate'', ''interstate'', ''intersrate''] , pero esto sería:
>>> index = len(
filter(lambda l: l[0] == l[1],
[ x for x in enumerate(
[i for i in range(min(map(len, a)))
if len(set(map(lambda e: e[i], a))) == 1]
)]))
>>> a[0][:index]
inters