spot7.org logo
Home PHP C# C++ Android Java Javascript Python IOS SQL HTML Categories

Run time of reversing the words in a string


In your algorithm:

  • split has linear complexity in the length of the input string

  • Assuming that by

    string wordsReversed;
    

    you actually meant

    string wordsReversed = "";
    

    and that by

    wordsReversed.join(" ", reversedWord);
    

    you actually meant

    wordsReversed += " " + reversedWord;
    

    then the body of the outer foreach loop has linear complexity in the length of word since both the inner foreach loop and the concatenation of reversedWord with wordsReversed have linear complexity in the length of word.

  • Finally, the sum of the lengths of all the words in words is the length of the initial input string

Therefore your total complexity is O(n), as it should be.

Also, "a b c d e f g h i j k l m n o p" is not a worst case scenario for this algorithm, for the reasons mentioned above, although the algorithm would indeed be somewhat inefficient in that case.


Categories : Algorithm

Related to : Run time of reversing the words in a string
Solution critique: reversing words in a sentence
Except the comment, to use a more efficient data structure (StringBuilder) to create the string, I don't think there is much you can do. The time complexity to reverse an array is n/2 (How do I reverse an int array in Java?) but afterwards you would still need to concatenate all of the items, which should be n - since you're concatenating them right away you get down from 3n/2 to only n.

Categories : Java
Displaying the Top 10 words in a string
Use collections.Counter to count all the words, Counter.most_common(10) will return the ten most common words and their count wordz = v.split() from collections import Counter c = Counter(wordz) print(c.most_common(10)) Using with to open the file and get a count of all the words in the txt file: from collections import Counter with open("http://www.textfiles.com/etext/FICTION/alice30.txt") as

Categories : Python
preg_replace same words in a string
Use the below regex in preg_replace function. Regex: (:wall:)(?:s+:wall:)+ OR (:wall:)(?:s+1)+ Replacement string: $1 DEMO Code: <?php $str = "this is text :wall: :wall: :wall: :wall: more text"; echo preg_replace('~(:wall:)(?:s+1)+~', '$1', $str); ?> Output: this is text :wall: more text (:wall:) Captures the text :wall: into a group. This could be referred by group index 1

Categories : PHP
Copy words from c-string into 2D array of c-strings
Try adding a terminating null character to the end of your C strings when copying into the 2D array. In C string are represented by arrays of characters terminated by a '' character. The strange codes you are seeing are likely the result of the '' not being encountered and the print running of the end of the character array.

Categories : C++
assembly find words that contain substring in given string
The next instructions are not correct. "mov ebx,[esp+16];" "mov eax,[esp+12];" Use EBP in stead of ESP to process your parameters. This syntax does not exist. What do aim to accomplish? "mov [ecx,esp+8];" What do you think the jz reset will act upon? The ZF defined after cmp dl,dh is destroyed by inc ebx. "cmp dl,dh;" "inc ebx;" "jz reset;"

Categories : String
Recently Add
why this assembly piece of code do jmp forever
Find out if segment is fully inside of polygon
Algorithm for coloring a hexagon tile map with minimum distance (3) for reoccurring colors
Sort pairs to be more consecutive
To find three unique numbers whose number of occurrence is even
Dealing with duplication between unit and integration tests
reflection and symmetry in back tracking queens
Big O analysis for method with multiple parameters
Divide Huge Array of Numbers in Buckets
Algorithm to find adjacent cells in a matrix
Why this code gives WA for Petersen Graph(codechef)?
Complexity of this prime number search algorithm
How to detect if a file has changed?
Given string x,y and z. Determine if z is a shuffle
Basic decryption for simple encryption algorithm
An efficient way to assign user_ids to huge dataset under certain conditions
What's a more efficient implementation of this puzzle?
Generating prime numbers in poly-time
What if I do not use G transpose in calculating Strongly Connected Components?
Dividing an array into optimum no of equal sum sublists
Counting derangements
How to iterate through all cases when partitioning objects
Algorithm: How to find closest element, having coordinates and dimension
Developing player rankings with ELO
How to transform two set of discrete points ( vectors ) to help plotting them on a common scale
Heap Sort Space Complexity
complex root finding algorithm
Every possible combination algorithm
RSA Cryptosystem - Retrieve m
Heap-like data structure with fast random access?
© Copyright 2017 spot7.org Publishing Limited. All rights reserved.