990. Satisfiability of Equality Equations ⭐

Medium

You are given an array of strings equations that represent relationships between variables where each string equations[i] is of length 4 and takes one of two different forms: "xi==yi" or "xi!=yi".Here, xi and yi are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if it is possible to assign integers to variable names so as to satisfy all the given equations, or false otherwise.

Example 1:

Input: equations = ["a==b","b!=a"]
Output:
 false
Explanation:
 If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second.
There is no way to assign the variables to satisfy both equations.

Example 2:

Input: equations = ["b==a","a==b"]
Output:
 true
Explanation:
 We could assign a = 1 and b = 1 to satisfy both equations.

Constraints:

• 1 <= equations.length <= 500

• equations[i].length == 4

• equations[i][0] is a lowercase letter.

• equations[i][1] is either '=' or '!'.

• equations[i][2] is '='.

• equations[i][3] is a lowercase letter.

解題

Runtime: 0 ms, faster than 100%

Memory Usage: 0 MB, less than 100%

func equationsPossible(equations []string) bool {
    arr := make([]int, 26)
    for i:=0; i<26; i++ {
        arr[i] = i
    }

    for _, eq := range equations {
        if eq[1] == '!' { continue }
        arr[find(arr, int(eq[0] - 'a'))] = find(arr, int(eq[3] - 'a'))
    }

    for _, eq := range equations {
        if eq[1] == '=' { continue }
        if arr[find(arr, int(eq[0] - 'a'))] == arr[find(arr, int(eq[3] - 'a'))] {
            return false
        }
    }

    return true
}

func find(arr []int, x int) int {
    if arr[x] == x {
        return x
    } 
    return find(arr, arr[x])
}