Skip to content

reducing complexity to linear complixity #2087

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Feb 21, 2021

Conversation

Itayventura
Copy link
Contributor

Why I replaced the solution?

The original solution works. but runs at complexity of O(N*log(N))
whereas N := max(s1.length(), s2,length) [maximum length of two Strings]
the complexity of N*log(N) is due to sorting the character array.
my solution runs at a linear complexity, O(N).
instead of sorting, I use an HashMap, and 3 successive loops.

My solution

  1. I initialize the hash map.
  2. first loop: I count the number of appearances in the first String and update the hashmap. I do that by iterating through the characters. if a character has not appeared yet, I put the value of 1. otherwise I add 1 to its value.
  3. second loop: I iterate through each character in the second string. if a character does not appear in the hashmap. I return false. Otherwise, I reduce its value by 1.
  4. third loop: I iterate over the values in the hashmap. If there is a different value rather than 0. I return false.
  5. if we reached to the end of the function then return true.

@stale
Copy link

stale bot commented Feb 16, 2021

This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@stale stale bot added the stale label Feb 16, 2021
@stale stale bot removed the stale label Feb 21, 2021
@yanglbme yanglbme merged commit a475463 into TheAlgorithms:master Feb 21, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants