Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
May 29, 2022 03:54 am GMT

Find all substring of a given string in O(n^2) time.

Below is the programmer written in JavaScript to find the all possible substrings of a given string in O(N^2) time complexity and an extra O(1) space;

Programme

function genSubstrings(inputString){    debugger;    let resultArray = [];    // outer loop to run n times [n = size of string]    for(let i = 0; i < inputString.length; i++){        // pushing first char of string as substring        // as we know that each char will be substring itself too.        resultArray.push(inputString[i]);        // inner loop to run n - 1 times;        for(let j = i + 1; j < inputString.length; j++){            // get last substring and append the new next char            resultArray.push(              resultArray[resultArray.length - 1] + inputString[j]            );        }    }    return resultArray;}

Output

genSubstrings("abcd");(10)['a', 'ab', 'abc', 'abcd', 'b', 'bc', 'bcd', 'c', 'cd', 'd']


I searched internet for a better solution which can run in less then O(N^2) time complexity but didn't find any.

If anyone has a better solution please write in comments, It will be really helpful.

The thumbnail is taken from geekforgeek


Original Link: https://dev.to/rajeshroyal/find-all-substring-of-a-given-string-in-on2-time-2ip7

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To