DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Newsletter
Log In / Join
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Related

  • Commonly Occurring Errors in Microsoft Graph Integrations and How To Troubleshoot Them (Part 4)
  • Build a Java Microservice With AuraDB Free
  • Mastering Concurrency: An In-Depth Guide to Java's ExecutorService
  • Optimizing Java Applications: Parallel Processing and Result Aggregation Techniques

Trending

  • Why 200 OK Is the Most Dangerous Lie in Enterprise Integration
  • Mastering Load Balancers: Optimizing Traffic for High Availability and Performance
  • Testing AI-Infused Apps: A Dual-Layer Framework for AI Quality Assurance
  • 5 AI Security Incidents That Broke Things in Production (and What They Have in Common)

Draft This article hasn't been published, so readers can't see it.

In moderation This article is waiting for review, so readers can't see it yet.

Deleted This article has been deleted, so readers can't see it.

  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Permutation Check in Java

Permutation Check in Java

Check out this post to learn more about solving permutation check problems in Java.

By 
Zoltan Raffai
·
Jun. 17, 19 · Presentation
Post on X (opens in a new tab) Share on LinkedIn (opens in a new tab)
15.8K Views

Join the DZone community Save articles, join the discussion, and download Refcards and Trend Reports with a free account.

Join for free Already a member? Log in

Here is a new Algorithm problem continuing our season. If you missed the first article, check it here: Decide if a String has duplicates.

Our next problem description is the following:

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

Here, we should ask the following questions:

  • Is the permutation comparison case sensitive?
    • That means: dog equal to Dog?
  • We should ask if whitespace characters are significant?
  • What is the character coding?

Our assumption is that our comparison is case sensitive, whitespaces are significant, and we use ASCII.

Solution #1

Think about the difference between two strings and whether they are the permutations of each other. The solution is simple: They have the same character count and only the character order differs.

If you find this statement, the task becomes quite straightforward.

We just need to compare the sorted versions of the strings.

        private static final String perm1 = "abcdefga";
private static final String perm2 = "abcdfega";


private String sort(String s) {

char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}

public Boolean getIsPermutations() {
if(perm1.length() != perm2.length()) return false;
return sort(perm1).equals(sort(perm2));
}


Although the above example is very clean and simple, performance is very important, so we may need to implement it in a different way.

Solution #2

We can implement an algorithm through the definition of "two words with the same character counts."

The below algorithm counts how many times each character appears, and then, it compares the two arrays.

boolean permutation(String s, String t) {
  if (s.length() != t.length()) {
    return false;
  }
  int[] letters = new int[128];// Assumption that it is in ASCII, you should always care about it.
  char[] s_array = s.toCharArray();
  for (char c : s_array) { // count number of each char in s.
    letters[c]++;
  }
  for (int i= 0; i < t.length(); i++) {
    int c = (int) t.charAt(i);
    letters[c]--;
    if (letters[c] < 0) {
      return false;
    }
  }
return true; 
}


Notes

Hope you enjoyed my latest programming puzzle. I recommend you to try to solve them before going through the solution.

And feel free to share your ideas in the comments below.

This problem is from the Cracking the Coding Interview book, which I wrote about under the Resources menu.

Java (programming language) Strings Algorithm Comparison (grammar) Coding (social sciences) ASCII Data Types Task (computing) Book

Published at DZone with permission of Zoltan Raffai. See the original article here.

Opinions expressed by DZone contributors are their own.

Related

  • Commonly Occurring Errors in Microsoft Graph Integrations and How To Troubleshoot Them (Part 4)
  • Build a Java Microservice With AuraDB Free
  • Mastering Concurrency: An In-Depth Guide to Java's ExecutorService
  • Optimizing Java Applications: Parallel Processing and Result Aggregation Techniques

Partner Resources

×

Comments

Loading comments

The comments didn't load

Please try again in a moment.

Likes

Loading

The next likes didn't load. Please try again.

The likes didn't load

Please try again in a moment.

See who liked this

Log in or join DZone for free to see who liked this article.

Log in Join for free
  • RSS
  • X
  • Facebook

ABOUT US

  • About DZone
  • Support and feedback
  • Community research

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 215
  • Nashville, TN 37211
  • [email protected]

Let's be friends:

  • RSS
  • X
  • Facebook