2022-05-17

[Zheaoli]

2022-05-17

[SaraadKun]

953. 验证外星语词典

class Solution {

    int[] dict = new int[26];
    public boolean isAlienSorted(String[] words, String order) {
        for (int i = 0; i < 26; i++) {
            dict[order.charAt(i) - 'a'] = i;
        }
        for (int i = 1; i < words.length; i++) {
            if (!valid(words[i - 1], words[i])) {
                return false;
            }
        }
        return true;

    }

    private boolean valid(String first, String second) {
        int n1 = first.length(), n2 = second.length();
        for (int i = 0; i < n1 && i < n2; i++) {
            char ch1 = first.charAt(i);
            char ch2 = second.charAt(i);
            if (ch1 == ch2) {
                continue;
            }
            return dict[ch1 - 'a'] <= dict[ch2 - 'a'];
        }
        return n1 <= n2;
    }
}

---

WeChat:Saraad

[dreamhunter2333]

package main

/*
 * @lc app=leetcode.cn id=953 lang=golang
 *
 * [953] 验证外星语词典
 */

// @lc code=start
import (
    "fmt"
    "reflect"
    "sort"
)

func Min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

type byAlien struct {
    s        []string
    orderMap map[byte]int
}

func (b byAlien) Len() int {
    return len(b.s)
}
func (b byAlien) Swap(i, j int) {
    b.s[i], b.s[j] = b.s[j], b.s[i]
}

func (b byAlien) Less(i, j int) bool {
    for k := 0; k < Min(len(b.s[i]), len(b.s[j])); k++ {
        first := b.orderMap[b.s[i][k]]
        second := b.orderMap[b.s[j][k]]
        if first != second {
            return first < second
        }
    }
    return len(b.s[i]) < len(b.s[j])
}

func isAlienSorted(words []string, order string) bool {
    orderMap := make(map[byte]int)
    for i := 0; i < len(order); i++ {
        orderMap[order[i]] = i
    }
    newWords := make([]string, len(words))
    copy(newWords, words)
    sort.Sort(byAlien{newWords, orderMap})
    return reflect.DeepEqual(words, newWords)
}

// @lc code=end
func main() {
    fmt.Println(isAlienSorted(
        []string{"apple", "app"}, "abcdefghijklmnopqrstuvwxyz"))
    fmt.Println(isAlienSorted(
        []string{"hello", "leetcode"}, "hlabcdefgijkmnopqrstuvwxyz"))
    fmt.Println(isAlienSorted(
        []string{"word", "world", "row"}, "worldabcefghijkmnpqstuvxyz"))
}

---

微信id: 而我撑伞 来自 vscode 插件