practice-algorithms/is-alien-sorted.js at master · denniswritescode/practice-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
var l = console.log;
/**
 * @description https://leetcode.com/problems/verifying-an-alien-dictionary/
 * @repo https://github.com/dennisporterjr/practice-algorithms/blob/master/is-alien-sorted.js
 * @param {string[]} words
 * @param {string} order
 * @return {boolean}
 */
var isAlienSorted = function(words, order) {
    let wordTable = {};
    let letterTable = {};
    let orderIndex = {};
    let first;
    let second;

    for(let i = 0; i < words.length-1; i++) {
        let firstWord = words[i];
        let secondWord = words[i+1];
        let firstWordLength = firstWord.length;
        let wHash = firstWord + "|" + secondWord;

        if(wordTable[wHash]) continue;
        if(firstWord === secondWord) continue;
        if(firstWord.startsWith(secondWord)) return false;
        if(secondWord.startsWith(firstWord)) continue;

        for(let j = 0; j < firstWordLength; j++) {
            let a = firstWord[j];
            let b = secondWord[j];
            let lHash = a + "|" + b;

            if(letterTable[lHash] === "same") continue;
            if(letterTable[lHash] === "compared") break;

            if(orderIndex[a]) {
                first = orderIndex[a];
            } else {
                first = order.indexOf(a);
                orderIndex[a] = first;
            }

            if(orderIndex[b]) {
                second = orderIndex[b];
            } else {
                second = order.indexOf(b);
                orderIndex[b] = second;
            }

            if(first < second && j === 0) break;

            if(first > second) {
                return false;
            } else if(firstWord[j] !== secondWord[j]) {
                letterTable[lHash] = "compared";
                break;
            }

            letterTable[lHash] = "same";
        }

        wordTable[wHash] = true;
    }

    return true;
};

// var words = ["apap","app"];
// var order = "abcdefghijklmnopqrstuvwxyz";
var words = ["fxasxpc","dfbdrifhp","nwzgs","cmwqriv","ebulyfyve","miracx","sxckdwzv","dtijzluhts","wwbmnge","qmjwymmyox"];
var order = "zkgwaverfimqxbnctdplsjyohu";
l(isAlienSorted(words, order))