Clever Geek Handbook

Manually calculate string length

I have a homework assignment requesting to calculate the length of a string without using inline functions.

I meant to use a counter:

s = 0
while name[s] != "":
    s += 1

but i'm stuck on how to solve the error string index out of range

... or is there any other way?

+3


source to share


5 answers


you have two simple options:

Or add a sentence try/except

:

s = 0
try:
    while(name[s]):
       s += 1
except IndexError:
    pass
print(s)


Or use an iterator:

s = 0
for _ in name:
    s += 1
print(s)
+3


source


Try it,



counter = 0
st = 'ABCDEF'
for i in st:
    counter += 1

print('Length of String is : ', str(counter))
+1


source


So, a string is basically a sequence of characters. For example:

'hello' = ['h', 'e', 'l', 'l', 'o']

So, if you just loop through this array and add each loop 1

to the variable length

, you get the length:

string = "hello"
length = 0
for character in string:
  length = length + 1
print(length)

This way you don't even have to worry about handling exceptions :)

Try online

https://repl.it/IptA/0

additional literature

Strings

Lists

0


source


There is an alternative to "silly" calculations, adding one for each character:

  • Exponential search finds a range of string length.
  • Binary search concatenates the length of the string starting from the range found in the previous step.

Test section code:

def is_valid_index(s, i):
    '''Returns True, if i is a valid index of string s, and False otherwise.'''
    try:
        s[i]
        return True
    except IndexError:
        return False

def string_length(s):
    '''Returns the length of string s without built-ins.'''
    # Test for empty string (needed for the invariant
    # of the following exponential search.)
    if not is_valid_index(s, 0):
        return 0

    # Exponential search with low as inclusive lower bound
    # and high as exclusive upper bound.
    # Invariant for the loop: low is a valid index.
    low = 0
    high = 1
    while True:
        if is_valid_index(s, high):
            low = high
            high *= 2
            continue

        break

    # Binary search inside the found range
    while True:
        if low + 1 == high:
            return high

        middle = (low + high) // 2
        if is_valid_index(s, middle):
            low = middle
        else:
            high = middle


# Test section
print(string_length('hello'))

# Test the first thousand string lengths
for i in range(1000):
    s = 'x' * i
    if len(s) != string_length(s):
        print('Error for {}: {}'.format(i, string_length(s)))

# Test quite a large string
s = 'x' * 1234567890
print(string_length(s))

Result:

5
1234567890
0


source


The string has an attribute __len__

, a function that returns the length of the string. So the following solution does not use built-in modules, but the computation is trivial (no computation of operations, hence this might not be the goal of homework):

def get_string_length(s):
    return s.__len__()

Test:

print(get_string_length('hello'))

Result:

5
-1


source






More articles:


All Articles