Skip to content

Instantly share code, notes, and snippets.

@spiralx

spiralx/is-anagram.js

Last active August 20, 2021 12:55
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save spiralx/10aa33a676e6e3af88941915219129f4 to your computer and use it in GitHub Desktop.
Save spiralx/10aa33a676e6e3af88941915219129f4 to your computer and use it in GitHub Desktop.
Download ZIP
A bunch of methods for checking if two strings are anagrams of each other
Raw
is-anagram.js
(() => {
function run(fns, a, b, exp, gn, iters = 100000) {
console.group(gn)
for (const fn of fns) {
const name = fn.name
if (fn(a, b) !== exp) {
console.warn(`ERROR: ${name}('${a}', '${b}') = %o`, fn(a, b))
} else {
console.time(name)
for (let i = 0; i < iters; i++) {
fn(a, b)
}
console.timeEnd(name)
}
}
console.groupEnd()
}
// ----------------------------------------------------------
// sorted most used characters in english mapped to indexes
const CHAR_ORDER = [ 4, 0, 17, 8, 14, 19, 13, 18, 11, 2, 20, 3, 15, 12, 7, 6, 1, 5, 24, 22, 10, 21, 23, 25, 9, 16 ]
// ----------------------------------------------------------
function isAnagram(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
return a.toLowerCase().split('').sort().join('') === b.toLowerCase().split('').sort().join('')
}
// ----------------------------------------------------------
function isAnagram2(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const getCharIndex = (s, i) => {
const ci = s.charCodeAt(i)
return ci >= 97 ? ci - 97 : ci - 65
}
const numChars = Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ getCharIndex(a, i) ]++;
numChars[ getCharIndex(b, i) ]--
}
return numChars.every(v => v === 0)
}
// ----------------------------------------------------------
function isAnagram3(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const getCharIndex = (s, i) => {
const ci = s.charCodeAt(i)
return ci >= 97 ? ci - 97 : ci - 65
}
const numChars = Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ getCharIndex(a, i) ]++;
numChars[ getCharIndex(b, i) ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram4(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const getCharIndex = (s, i) => (s.charCodeAt(i) - 65) % 32
const numChars = Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ getCharIndex(a, i) ]++;
numChars[ getCharIndex(b, i) ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram5(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram5Uint16Array(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Uint16Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram9(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Uint16Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
const charPriority = [ 4, 0, 17, 8, 14, 19, 13, 18, 11, 2, 20, 3, 15, 12, 7, 6, 1, 5, 24, 22, 10, 21, 23, 25, 9, 16 ]
for (let i = 0; i < 26; i++) {
if (numChars[ charPriority[ i ] ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram9a(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Uint16Array(26).fill(0)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ CHAR_ORDER[ i ] ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram10(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Uint16Array(26)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram11(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Uint8Array(26)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram12(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
const numChars = new Int16Array(26)
for (let i = 0; i < a.length; i++) {
numChars[ (a.charCodeAt(i) - 65) % 32 ]++;
numChars[ (b.charCodeAt(i) - 65) % 32 ]--
}
for (let i = 0; i < 26; i++) {
if (numChars[ i ] !== 0) {
return false
}
}
return true
}
// ----------------------------------------------------------
function isAnagram6(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
let av = 0, bv = 0
for (let i = 0; i < a.length; i++) {
av += (a.charCodeAt(i) - 65) % 32
bv += (b.charCodeAt(i) - 65) % 32
}
return av === bv
}
// ----------------------------------------------------------
function articleIsAnagram(a, b) {
const buildMap = s => {
const cm = {}
for (let char of s.toLowerCase()) {
cm[ char ] = (cm[ char ] ?? 0) + 1
}
return cm
}
const amap = buildMap(a), bmap = buildMap(b)
if (Object.keys(amap).length !== Object.keys(bmap).length) {
return false
}
for (const ch in amap) {
if (amap[ ch ] !== bmap[ ch ]) {
return false
}
}
return true
}
// ----------------------------------------------------------
function showBitsUsed(numChars) {
const bitsPerChar = Math.ceil(Math.log2(numChars)), out = []
for (let i = 1; i <= numChars; i++) {
const uniquePercent = (100 * (i / numChars)).toFixed() + '%'
out.push({ numChars, bitsPerChar, uniqueChars: i, uniquePercent, bitsUsed: bitsPerChar * i, ok: bitsPerChar * i < 53 ? '✔️' : '❌' })
}
console.table(out)
}
function isAnagram8(a, b) {
if (a.length !== b.length) {
return false
} else if (a.length === 0) {
return true
}
// Calculate the no. of bits needed to count how many
// times any character appears in our strings.
const numChars = a.length
const bitsPerChar = Math.ceil(Math.log2(numChars))
// const _mask = Math.pow(2, bitsPerChar) - 1
// const incValAt = (val, offset) => val + (1 << offset)
// const getValAt = (val, offset) => (val & (_mask << offset)) >> offset
let av = 0
let bv = 0
const offsets = Array(26)
let nextOffset = 0
/**
* First character we find gets its count stored in the BPC least
* significant bits of our bitfield, each new character to count
* occupies the next BPC bits above that.
*
* Limits bitfield size to at worst `bitsPerChar * numChars` when
* every character is different from all of those preceding it,
* the showBitsUsed method above will show limits due to JS integers
* having 53 usable bits of storage. 13 character strings can have
* 100% unique characters, it's ~80% for 16 chars, ~50% for 20 chars,
* ~33% for 30 chars, ~20% for 40 chars and so on.
*/
const getOffset = ci => offsets[ ci ] ??= (bitsPerChar * nextOffset++)
for (let i = 0; i < numChars; i++) {
const aOffset = getOffset((a.charCodeAt(i) - 65) % 32)
av += 1 << aOffset
const bOffset = getOffset((b.charCodeAt(i) - 65) % 32)
bv += 1 << bOffset
}
return av === bv
}
// ----------------------------------------------------------
function ashishIsAnagram(a, b) {
let hashCodeA = 0
let hashCodeB = 0
let purgedStrA = a?.toLowerCase()//.replace(/\s/g, '')
let purgedStrB = b?.toLowerCase() //.replace(/\s/g, '')
if((purgedStrA && purgedStrB) && (purgedStrA.length != purgedStrB.length))
{
return false
}
for(i=0;i<purgedStrA.length;i++)
{
const charCodeA = purgedStrA.charCodeAt(i)
const charCodeB = purgedStrB.charCodeAt(i)
if(charCodeA!=32)
{
hashCodeA += charCodeA*31
}
if(charCodeB!=32)
{
hashCodeB += charCodeB*31
}
}
return hashCodeA == hashCodeB
}
// ----------------------------------------------------------
function joseIsAnagram(a, b) {
const aGrouped = groubByChar(a)
const bGrouped = groubByChar(b)
if (aGrouped.size !== bGrouped.size) return false;
for (const [k, v] of aGrouped.entries()) {
if (!bGrouped.has(k) || (bGrouped.get(k) !== v) ) return false;
}
return true
}
function groubByChar(str) {
let outp_map = new Map();
for(let i = 0; i < str.length; i++) {
let k = str[ i ].toLowerCase()
let c = outp_map.has(k) ? outp_map.get(k) : 0
outp_map.set(k, c + 1)
}
return outp_map
}
function joseIsAnagram2(a, b) {
if (a.length !== b.length) return false
let aGrouped = new Map()
let bGrouped = new Map()
for(let i = 0; i < a.length; i++) {
const ka = a[ i ].toLowerCase()
const kb = b[ i ].toLowerCase()
const ca = aGrouped.has(ka) ? aGrouped.get(ka) : 0
const cb = bGrouped.has(kb) ? bGrouped.get(kb) : 0
aGrouped.set(ka, ca + 1)
bGrouped.set(kb, cb + 1)
}
if (aGrouped.size !== bGrouped.size) return false
for (const [k, v] of aGrouped.entries()) {
if (!bGrouped.has(k) || (bGrouped.get(k) !== v) ) return false
}
return true
}
function joseIsAnagram3(a, b) {
if (a.length !== b.length) return false
let aGrouped = new Map()
let bGrouped = new Map()
for(let i = 0; i < a.length; i++) {
const ka = (a.charCodeAt(i) - 65) % 32
const kb = (b.charCodeAt(i) - 65) % 32
const ca = aGrouped.has(ka) ? aGrouped.get(ka) : 0
const cb = bGrouped.has(kb) ? bGrouped.get(kb) : 0
aGrouped.set(ka, ca + 1)
bGrouped.set(kb, cb + 1)
}
if (aGrouped.size !== bGrouped.size) return false
for (const [k, v] of aGrouped.entries()) {
if (!bGrouped.has(k) || (bGrouped.get(k) !== v) ) return false
}
return true
}
function joseIsAnagram4(a, b) {
if (a.length !== b.length) return false
let aGrouped = new Array(32).fill(0)
let bGrouped = new Array(32).fill(0)
for(let i = 0; i < a.length; i++) {
aGrouped[ (a.charCodeAt(i) - 65) % 32 ]++
bGrouped[ (b.charCodeAt(i) - 65) % 32 ]++
}
return aGrouped.every((a, i) => a === bGrouped[ i ])
}
function joseIsAnagram5(a, b) {
if (a.length !== b.length) return false
let aGrouped = new Uint16Array(26).fill(0)
let bGrouped = new Uint16Array(26).fill(0)
for(let i = 0; i < a.length; i++) {
aGrouped[ (a.charCodeAt(i) - 65) % 32 ]++
bGrouped[ (b.charCodeAt(i) - 65) % 32 ]++
}
// sorted most used characters in english mapped to indexes
const charPriority = [ 4, 0, 17, 8, 14, 19, 13, 18, 11, 2, 20, 3, 15, 12, 7, 6, 1, 5, 24, 22, 10, 21, 23, 25, 9, 16 ]
for (const i of charPriority) {
if (aGrouped[ i ] !== bGrouped[ i ]) return false
}
return true
}
function joseIsAnagram6(a, b) {
if (a.length !== b.length) return false
let aGrouped = new Uint16Array(26).fill(0)
let bGrouped = new Uint16Array(26).fill(0)
for(let i = 0; i < a.length; i++) {
aGrouped[ (a.charCodeAt(i) - 65) % 32 ]++
bGrouped[ (b.charCodeAt(i) - 65) % 32 ]++
}
for (const i of CHAR_ORDER) {
if (aGrouped[ i ] !== bGrouped[ i ]) return false
}
return true
}
// ----------------------------------------------------------
const allFuncs = [
isAnagram,
// isAnagram2,
// isAnagram3,
// isAnagram4,
isAnagram5,
isAnagram5Uint16Array,
isAnagram9,
// isAnagram5Uint16ArrayOrder,
// isAnagram10,
// isAnagram11, NO CHANGE
isAnagram12,
// isAnagram5Uint16ArrayOrder2, NO CHANGE
// isAnagram6, FAIL
// isAnagram8, LIMITED
// articleIsAnagram,
// ashishIsAnagram, FAIL
joseIsAnagram,
// joseIsAnagram2,
// joseIsAnagram3, MINE
// joseIsAnagram4,
joseIsAnagram5,
// joseIsAnagram6, MINE
]
console.clear()
run(allFuncs, '', '', true, 'empty strings')
// run(allFuncs, 5, 6, false, 'not strings')
run(allFuncs, 'Mary', 'Thingy', false, 'different lengths')
run(allFuncs, 'Mary', 'Army', true, '4 chars, true')
run(allFuncs, 'Mazz', 'Army', false, '4 chars, false')
run(allFuncs, 'aaau', 'ffff', false, '4 chars, false')
run(allFuncs, 'resistant', 'STRAITENS', true, '9 chars, true')
run(allFuncs, 'resistant', 'STRATTENS', false, '9 chars, false')
run(allFuncs, 'resistant', 'resistent', false, '9 chars, false')
run(allFuncs, 'hydroxydeoxycorticosterones', 'hydroxydesoxycorticosterone', true, '27 chars, true')
run(allFuncs, 'hydroxydeoxycorticosterones', 'hydroxycorticosteronelalone', false, '27 chars, false')
})()
Raw
solution-test-skeleton.js
(() => {
function run(fns, a, b, exp, gn, iters = 100000) {
console.group(gn)
for (const fn of fns) {
const name = fn.name
if (fn(a, b) !== exp) {
console.warn(`ERROR: ${name}('${a}', '${b}') = %o`, fn(a, b))
} else {
console.time(name)
for (let i = 0; i < iters; i++) {
fn(a, b)
}
console.timeEnd(name)
}
}
console.groupEnd()
}
// ----------------------------------------------------------
function isAnagram(a, b) {
// ...
}
// ----------------------------------------------------------
const allFuncs = [
isAnagram
]
console.clear()
run(allFuncs, 'Mary', 'Thingy', false, 'different lengths')
run(allFuncs, 'Mary', 'Army', true, 'true, 4 chars')
run(allFuncs, 'Mazz', 'Army', false, 'false, 4 chars')
run(allFuncs, 'resistant', 'STRAITENS', true, 'true, 9 chars')
run(allFuncs, 'resistant', 'resistent', false, 'false, 9 chars')
})()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment