# String Permutation

## Question

Given two strings, write a method to decide if one is a permutation of the other.
Example
abcd is a permutation of bcad, but abbe is not a permutation of abe

## Thinking

What is permutation and combinatorics? https://zh.wikipedia.org/wiki/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Permutation considers orders of elements while Combinatorics does not.

• null value doesnot meet requirement
• If A and B have different length, they don’t meet the requirement.
• Check B elements and make sure A has them.
• Remove found charactors in A to avoid misjudge duplicate charactors

## Java (Soution 1)

This solution’s time complexity is O(n) and very fast.

``````public class Solution {
/**
* @param A a string
* @param B a string
* @return a boolean
*/
public boolean stringPermutation(String A, String B) {
// check null value
if (A == null || B == null) {
return false;
}
// check length
if (A.length() != B.length()) {
return false;
}
// same strings
if (A.equals(B)) {
return true;
}
// convert string to char array
int[] aChars = new int[A.length()];
int[] cPostions = new int[128];
for (int i = 0; i < aChars.length; i++) {
aChars[i] = (int) A.charAt(i);
int bChar = (int) B.charAt(i);
cPostions[aChars[i]] = cPostions[aChars[i]] + 1;
cPostions[bChar] = cPostions[bChar] - 1;
}
for (int i = 0; i < aChars.length; i++) {
if (cPostions[aChars[i]] != 0) {
return false;
}
}
return true;
}
}
``````

## Java (solution 2)

This solution works but it needs more time. Time complexity is O(n2).

``````public class Solution {
/**
* @param A a string
* @param B a string
* @return a boolean
*/
public boolean stringPermutation(String A, String B) {
// check null value
if (A == null || B == null) {
return false;
}
// check length
if (A.length() != B.length()) {
return false;
}
// convert string to char array
char[] aChars = A.toCharArray();
char[] bChars = B.toCharArray();
// compare element in bChars
for (int i = 0; i < bChars.length; i++) {
boolean isFound = false;
for (int j = 0; j < aChars.length; j++) {
if (bChars[i] == aChars[j]) {
// found
aChars[j] = 0; // avoid duplicate chars
isFound = true;
break;
}
}
if (!isFound) {