An Interest In:
Web News this Week
- April 25, 2024
- April 24, 2024
- April 23, 2024
- April 22, 2024
- April 21, 2024
- April 20, 2024
- April 19, 2024
May 29, 2022 03:54 am GMT
Original Link: https://dev.to/rajeshroyal/find-all-substring-of-a-given-string-in-on2-time-2ip7
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:
Tweet
View Full Article
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To