LeetCode Weekly Contest 9第9週試合

422. Valid Word Square
Given a sequence of words, check whether it forms a valid word square.
A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns). Note: 1. The number of words given is at least 1 and does not exceed 500. 2. Word length will be at least 1 and does not exceed 500. 3.Each word contains only lowercase English alphabet a-z.概ねstring配列のセットを指定し、string配列が要求に合致するかどうかを判断する.ブロックを横に読むのと縦に読むのと同じように要求します.直接判断すればいい.golang ACコード:

func validWordSquare(words []string) bool {
    str := ""
    for i:=0 ;i< len(words);i++{
        str = ""
        for j:=0;j<len(words);j++{
            if i < len(words[j]){
                str += string(words[j][i])
            }else{
                break
            }
        }
        if str != words[i]{
            return false
        }

    }
    return true
}

423. Reconstruct Original Digits from English
Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.
Note: 1. Input contains only lowercase English letters. 2. Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted. 3. Input length is less than 50,000.
乱順のアルファベットシーケンスを与えて、このアルファベットシーケンスの再編成後に代表される数字列を求めます.例:

Input: "owoztneoer"

Output: "012"

タイトルの中で与えられたアルファベットのシーケンスは必ず合法的で唯一だと言っています.
この問題は主に0-9の英語で独占しているアルファベットに基づいて判断される.判断の順序は以下の通りである.
数値
英語
文字
0
zero
z
6
six
s
2
two
w
7
seven
s
4
four
u
5
five
v
1
one
o
9
nine
n
8
eight
i
3
three
t
表の第1項から,まずzの個数で0の個数を決定し,次にsで6の個数を決定することができる.順次類推する.9の個数はnの個数の半分であることに注意しなければならない.最後に乱順シーケンスの元の数字の組み合わせが得られる.golang ACコード:

func originalDigits(s string) string {
    nums := []string{"zero","one","two","three","four","five","six","seven","eight","nine"}
    var count [10]int
    var acount [26]int
    for i:=0;i<len(s);i++{
        acount[int(s[i]-'a')] ++
    }
    if acount[25]>0{
        str := nums[0]
        count[0] = acount[25]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[0]
        }
    }
    if (acount[int('x'-'a')]>0){
        str := nums[6]
        count[6] = acount[int('x'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[6]
        }
    }
    if (acount[int('w'-'a')]>0){
        str := nums[2]
        count[2] = acount[int('w'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[2]
        }
    }

    if (acount[int('s'-'a')]>0){
        str := nums[7]
        count[7] = acount[int('s'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[7]
        }
    }
    if (acount[int('u'-'a')]>0){
        str := nums[4]
        count[4] = acount[int('u'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[4]
        }
    }
    if (acount[int('v'-'a')]>0){
        str := nums[5]
        count[5] = acount[int('v'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[5]
        }
    }
        if (acount[int('o'-'a')]>0){
        str := nums[1]
        count[1] = acount[int('o'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[1]
        }
    }   
    if (acount[int('n'-'a')]>0){
        str := nums[9]
        count[9] = acount[int('n'-'a')]/2
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[9]
        }
    }
    if (acount[int('i'-'a')]>0){
        str := nums[8]
        count[8] = acount[int('i'-'a')]
        for i:=0;i<len(str);i++{
            acount[int(str[i]-'a')] -= count[8]
        }
    }
    count[3] = acount[int('r'-'a')]
    str := ""
    for i:=0;i<=9;i++{
        for j:=0;jstring(i+'0')
        }
    }
    return str
}

424. Longest Repeating Character Replacement
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations. 大文字のみからなる文字列と、数字kの列が与えられる.この文字列は最大k文字が他の文字に置き換えられると仮定する.この置換の過程の中で、最も長い連続的な繰り返しシーケンスの長さを求めます.この問題は列挙法を用いて,まず最長の連続を求めるAを仮定すると,シーケンス全体においてAではない点をすべて表記することができる.そして、これらの点のあるK個をAに変えるのを見てみましょう.この交換過程における最長長を求める.アルゴリズムの複雑度はo(n)である.MAC golangコードは以下の通りです.

func characterReplacement(s string, k int) int {
    dp := make([]int,len(s)+1)
    var ch [26]bool
    max := 0
    if k == 0{
        length := 1
        for i :=1;i<len(s);i++{
            if s[i-1] == s[i]{
                length ++
            }else{
                if max < length{
                    max = length
                }
                length = 1
            }

        }
        if max < length{
                    max = length
                }
        return max;
    }
    //length := 0
    for i :=0;i<len(s);i++{
        ch[s[i]-'A'] = true
    }
    for i :=0;i<26;i++{
        if ch[i] == false{
            continue
        }
        c := 'A' + i
    //  if c == 75{
    //      fmt.Println("break")
    //  }
        idx :=0
        for j:=0;j<len(s);j++{
            if int(s[j])!=c{
                dp[idx] = j
                idx++
            //else{
        //      fmt.Print(j," ")
            }
        }
        //fmt.Println("|",c)
        if idx <= k{
            return len(s)
        }
        if max < dp[k]{
            max = dp[k]
        }
        for j:= k+1;j if dp[j] - dp[j-k-1] - 1 >= max{
                max = dp[j] - dp[j-k-1] - 1
                //fmt.Println(c)
            }
        }
    }
    return max
}

425 Word Squares
できなかったので、他の人のpythonコードを貼って、trieツリーにdfsを追加しました.

class Solution(object):
    def wordSquares(self, words):
        """
        :type words: List[str]
        :rtype: List[List[str]]
        """
        self.l = len(words[0])

        self.trie = self.build(words)

        self.res = []

        for word in words:
            self.dfs(words, self.trie, [word])

        return self.res

    def dfs(self, words, trie, lst):
        if len(lst) == self.l:
            self.res.append(lst)
            return

        prefix = ''
        for i in range(len(lst)):
            prefix += lst[i][len(lst)]

        for s in self.get(trie, prefix):
            self.dfs(words, trie, lst + [s])


    def build(self, words):
        trie = {}

        for word in words:
            t = trie

            for c in word:
                if c not in t:
                    t[c] = {}
                t = t[c]

            t['#'] = '#'

        return trie


    def get(self, trie, prefix):
        res = []

        t = trie
        for c in prefix:
            if c not in t:
                return res
            t = t[c]

        for s in self.getall(t):
            res.append(prefix + s)

        return res

    def getall(self, t):
        res = []
        if '#' in t: return ['']

        for c in t:
            if c != '#':
                for s in self.getall(t[c]):
                    res.append(c + s)
        return res