Skip to content

Instantly share code, notes, and snippets.

@xealgo
Last active September 4, 2017 06:54
Show Gist options
  • Save xealgo/73e7eb52e1d41855908000c36671fde7 to your computer and use it in GitHub Desktop.
Save xealgo/73e7eb52e1d41855908000c36671fde7 to your computer and use it in GitHub Desktop.
checker permutation of a-z in O(n) time
// IsPermutation checks permutations in strings of a-z in O(n) time.
// O(n+n) since both a & b must be the same length.
func IsPermutation(a, b string) bool {
al, bl := len(a), len(b)
if al != bl {
return false
}
var checker [2]int
for i := 0; i < al; i++ {
// if the same char is encountered twice, it'll just
// set the same bit to 1 again.
checker[0] = checker[0] | (1 << uint(a[i]-97))
}
for i := 0; i < bl; i++ {
checker[1] = checker[1] | (1 << uint(b[i]-97))
}
//print the binary values of checkers a and b
//fmt.Printf("%b, %b\n", checker[0], checker[1])
return checker[0] == checker[1]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment