Paul Rubin>Still terrible. Use a better algorithm!<
I agree, it's O(n^2), but if you need to run this program just 1 time,
and the program is in C, and you don't want to use much time to think
and code a better algorithm (or you aren't able to do it) then maybe
that naive solution can be enough,
Paul Rubin wrote:
> [EMAIL PROTECTED] writes:
>>> I have suggested C because if the words are all of the same length then
>>> you have 3^2 = 90 000 000 000 pairs to test.
>> Sorry, you have (n*(n-1))/2 pairs to test (~ 45 000 000 000).
> Still terrible. Use a better algorithm!
To put all t
[EMAIL PROTECTED] writes:
> > I have suggested C because if the words are all of the same length then
> > you have 3^2 = 90 000 000 000 pairs to test.
>
> Sorry, you have (n*(n-1))/2 pairs to test (~ 45 000 000 000).
Still terrible. Use a better algorithm!
--
http://mail.python.org/mailman
> I have suggested C because if the words are all of the same length then
> you have 3^2 = 90 000 000 000 pairs to test.
Sorry, you have (n*(n-1))/2 pairs to test (~ 45 000 000 000).
bearophile
--
http://mail.python.org/mailman/listinfo/python-list
I think a way to solve the problem may be:
1) create a little Python script to separate the original words in many
files, each one containing only words of the same length. Every
filename can contain the relative word length.
2) write a little C program with two nested loops, that scans all the
pai
"John Machin" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
> In that case, the problem can be solved in O(n) time by a simple loop
> which counts the number of differences and notes the position of the
> first (if any) difference. Any full-distance Levenshtein method that
> does no
> Use the levenshtein distance.
Given the constraint that the two strings are the same length, I'm
assuming (as other posters appear to have done) that "vary by only one
character" precludes insertion and deletion operations.
In that case, the problem can be solved in O(n) time by a simple loop
w
manstey wrote:
> Is there a clever way to see if two strings of the same length vary by
> only one character, and what the character is in both strings.
>
> E.g. str1=yaqtil str2=yaqtel
>
> they differ at str1[4] and the difference is ('i','e')
>
> But if there was str1=yiqtol and str2=yaqtel,
manstey wrote:
> Hi,
>
> Is there a clever way to see if two strings of the same length vary by
> only one character, and what the character is in both strings.
You want zip.
def diffbyonlyone(string1, string2):
diffcount = 0
for c1, c2 in zip(string1, string2):
if c1 != c2:
manstey wrote:
> Hi,
>
> Is there a clever way to see if two strings of the same length vary by
> only one character, and what the character is in both strings.
>
> E.g. str1=yaqtil str2=yaqtel
>
> they differ at str1[4] and the difference is ('i','e')
>
> But if there was str1=yiqtol and str2=yaqt
manstey wrote:
> Hi,
>
> Is there a clever way to see if two strings of the same length vary by
> only one character, and what the character is in both strings.
>
> E.g. str1=yaqtil str2=yaqtel
>
> they differ at str1[4] and the difference is ('i','e')
something like this maybe?
>>> str1='yaqtil'
> Is there a clever way to see if two strings of the same length vary by
> only one character, and what the character is in both strings.
>
> E.g. str1=yaqtil str2=yaqtel
>
> they differ at str1[4] and the difference is ('i','e')
>
> But if there was str1=yiqtol and str2=yaqtel, I am not interes
Hi,
Is there a clever way to see if two strings of the same length vary by
only one character, and what the character is in both strings.
E.g. str1=yaqtil str2=yaqtel
they differ at str1[4] and the difference is ('i','e')
But if there was str1=yiqtol and str2=yaqtel, I am not interested.
can a
13 matches
Mail list logo
