CODEWITHSUNDEEP
pythonstring
Ann Z
Ann Z

Reputation: 33

Manually compute the length of a string

I have a homework assignment asking for string length calculation without using built-in functions.

What I had in mind is to use a counter:

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

but I'm stuck with how to solve the string index out of range error...or is there actually another way?

Upvotes: 3

Views: 160

Answers (5)

Heiko Oberdiek
Heiko Oberdiek

Reputation: 1708

There is an alternative to the "stupid" counting by adding one for each character:

  1. An exponential search finds a range for the string length.
  2. A binary search pins down the string length starting with the range, found in the previous step.

The code with test section:

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

Upvotes: 0

Heiko Oberdiek
Heiko Oberdiek

Reputation: 1708

A string has an attribute __len__, a function that returns the length of the string. Thus, the following solution does not use built-ins, but the calculation is trivial (without calculating operations, thus, it might be not the intention of the homework):

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

Test:

print(get_string_length('hello'))

Result:

5

Upvotes: -1

Anthony Rossi
Anthony Rossi

Reputation: 1262

you have two simple options :

Either add a try/except clause:

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)

Upvotes: 3

Noah Cristino
Noah Cristino

Reputation: 777

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 1 to your length variable every loop, you will get the length:

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

This way, you won't even need to worry about handling exceptions :)

Try it online

https://repl.it/IptA/0

Further Reading

Strings

Lists

Upvotes: 1

Stack
Stack

Reputation: 4526

Try this,

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

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

Upvotes: 1

Related Questions