CODEWITHSUNDEEP
phpstrlen
Yuri
Yuri

Reputation: 89

How to determine if a string is too long in O(1) time complexity?

I am trying to see if a string is over 10,000 characters. if it is, it should print too long. I know I can do this with strlen, but then the time complexity is O(n), which, isn't too bad, but I still have to iterate through 10,000 characters every time if someone enters 10,000 characters, but if my someone enters 1 million characters, thats a bad n. So My solution is, to check if the 10,001th character is set. If it is set, then its obviously too long. Would this work? Or would this sometimes work (and depends on how memory was/is being allocated).

Upvotes: 1

Views: 351

Answers (4)

Aakash Gandhi
Aakash Gandhi

Reputation: 55

<?php 
if (isset($str[100001])) { 
     ... do my stuff ... 
} ?>

The isset function is run on $str[10001] which is only one address in the array, hence o[1]. Also, while accessing key out of index in php, it does not throw error or cause memory leak. It throws an OutOfBoundsException exception which can be caught with a try catch block.

Upvotes: 0

shingo
shingo

Reputation: 27011

I know I can do this with strlen, but then the time complexity is O(n)

I don't know who tell you this, strlen is simply returns the len property.

Definition of strlen, it use ZSTR_LEN macro to get the string length

ZEND_FUNCTION(strlen)
{
    zend_string *s;

    ZEND_PARSE_PARAMETERS_START(1, 1)
        Z_PARAM_STR(s)
    ZEND_PARSE_PARAMETERS_END();

    RETVAL_LONG(ZSTR_LEN(s));
}

And the definition of ZSTR_LEN

#define ZSTR_LEN(zstr) (zstr)->len

Upvotes: 2

Icehorn
Icehorn

Reputation: 1337

strlen already has a time complexity of O(1), due to the fact that length is simply stored as an attribute.

http://php.net/manual/en/function.strlen.php

Upvotes: 1

Alvin Theodora
Alvin Theodora

Reputation: 946

Use substr

substr(yourString, lengthConstraint, 1);

Upvotes: 0

Related Questions