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\$ Commented Jul 5, 2016 at 19:02
  • \$\begingroup\$ there's an excellent oneliner implementation here: stackoverflow.com/questions/46613491/… \$\endgroup\$ Commented Oct 6, 2017 at 21:04

2 Answers 2

Reset to default
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\$ Commented Jul 6, 2016 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\$ Commented Feb 17, 2020 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\$ Commented Jul 5, 2016 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\$ Commented Jul 5, 2016 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\$ Commented Jul 5, 2016 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\$ Commented Jul 5, 2016 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\$ Commented Feb 17, 2020 at 4:29

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.