6
\$\begingroup\$

I've written some code to scan large files and search for long strings that you can write without repeating a letter. I'm self-taught in python and I'm wondering what I've missed.

import sys
letters ={} #letters is a dictionary
currentResult=""
ideas=[]
with open(sys.argv[1]) as f:
  while True:
    c = f.read(1)
    if not c:
      print "End of file"
      break
    if c in letters:
        letters={}
        temp=currentResult.rsplit(' ',1)[0]
        ideas.append(temp.rstrip('?:!.,;'))
        currentResult=""
    currentResult+=c
    if not c.isspace():
        letters[c]=True
ideas=sorted(set(ideas))
ideas.sort(lambda x,y: cmp(len(x), len(y)))
for x in ideas:
    print x.strip()
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Can you clarify the problem specification? There seem to be some space- and punctuation-handling behaviour that isn't naturally part of a "search for long strings". Also, the title says "the longest string", but the code actually prints many results. \$\endgroup\$ – 200_success Jul 5 '16 at 19:02
  • \$\begingroup\$ there's an excellent oneliner implementation here: stackoverflow.com/questions/46613491/… \$\endgroup\$ – Jean-François Fabre Oct 6 '17 at 21:04
4
\$\begingroup\$

I do believe the algorithm in the pervious answer and in the OP does not do what the OP wanted. It test for the longest string starting with the line's first character, and then repeat from the first non repeating string. For example if the string is

abcaefgb

The algorithm given will return

abc

while the right answer should be

bcaefg

I believe the following algorithm will find the right string. Note that if there are several equal length longest strings it will return the first

def scantillrepeat(line):
    found = ''
    for char in line:
        if not char in found:
            found = found + char
        else:
            break
    return found


def findlongest(f):
    for line in f:
        longestfound = ''
        longestfoundlen = 0
        for k in range(len(line)):
            candidate = scantillrepeat(line[k:])
            if len(candidate) > longestfoundlen:
                longestfound = candidate
                longestfoundlen = len(candidate)
    return longestfound

To test

In [39]: f = ['abcaefgb']

In [40]: findlongest(f)
Out[40]: 'bcaefg'

Note that my version does not allow joining lines separated by newline \n. This should be altered if needed.

\$\endgroup\$
2
  • \$\begingroup\$ return is not a function, it's a keyword (return(found) -> return found; return(longestfound) -> return longestfound) \$\endgroup\$ – 301_Moved_Permanently Jul 6 '16 at 7:29
  • \$\begingroup\$ For input "babad" I would expect to see "bad" as the longest string. How come your answer only find "ba"? \$\endgroup\$ – usustarr Feb 17 '20 at 4:30
2
\$\begingroup\$

Style

A good guide for style is PEP8. Basically, you want to put whitespace around operators and use underscores in variable names:

currentResult="" ==> current_result = ""

Your indentation is also a little unusual - 4 spaces per level of indentation is standard.

Process

I don't think letters needs to be a dictionary - you can just add letters to a list as you find them, and reset the list back to [] when you find a duplicate. I'd also avoid saving every single new combination you find - just save combinations that are longer than the current longest string.

When it comes to detecting if something is a character you want to use, I think you're working much harder than you need to. Importing the string module and making use of string.ascii_letters (or string.ascii_lowercase, etc) is much easier and more Pythonic.

Putting it together

I made a few assumptions:

  • If you find a non-letter character, stop adding characters to the longest string
  • Uppercase and lowercase characters count as different characters
  • Letters with accents are the same as letters without accepts (probably not a good assumption)

So here's my take on your code:

import sys
import string

with open(sys.argv[1]) as f:
    found = []
    longest = ""
    for line in f:
        for character in line:
            if character in string.ascii_letters and character not in found:
                found.append(character)
            else:
                if len(found) > len(longest):
                    longest = "".join(found)
                found = []
    print "Longest string found: {}".format(longest)
\$\endgroup\$
5
  • 1
    \$\begingroup\$ I have a small suggestion: test whether a character is a letter using character.isalpha() instead of character in string.ascii_letters. This way, it will work with all alphabetic characters, not only unaccented English letters. \$\endgroup\$ – Elias Zamaria Jul 5 '16 at 20:22
  • \$\begingroup\$ You had a comment about using sets and I thought it was a great idea - did you think of a reason why it didn't work? \$\endgroup\$ – Jeremy Weirich Jul 5 '16 at 20:23
  • \$\begingroup\$ Yes, I just noticed the "".join(found) line and realized that the order matters, so a set, which doesn't remember its elements in any definite order will not work properly. That is why I deleted my comment. \$\endgroup\$ – Elias Zamaria Jul 5 '16 at 20:24
  • 1
    \$\begingroup\$ Good point. Still, a set seems like a more attractive solution - perhaps it's time for the ordered set. \$\endgroup\$ – Jeremy Weirich Jul 5 '16 at 20:25
  • \$\begingroup\$ For input "babad" I would expect to see "bad" as the longest string. How come your answer only find "ba"? \$\endgroup\$ – usustarr Feb 17 '20 at 4:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.