[Medium] Array and Strings

Array and String type of questions were asked in interviews frequently. You will most likely encounter one during your interviews.
We recommend: Group Anagrams, Longest Substring Without Repeating Characters, Longest Palindromic Substring and Missing Ranges.
チャレンジ!!!

[1] 15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Notice that the solution set must not contain duplicate triplets.

My Answer 1: Accepted (Runtime: 2384 ms - 29.61% / Memory Usage: 17 MB - 97.17%)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return []
        
        nums.sort()
        
        result = set()
        
        for i in range(len(nums)):
            l = i+1
            r = len(nums)-1
            while l < r:
                three = nums[i] + nums[l] + nums[r]
                if three == 0:
                    result.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif three < 0:
                    l += 1
                else:
                    r -= 1
    
        return list(result)

三歳の習慣は80歳まで.最初は文三中を思い出しましたが・・・
元気を出して、sortの后で左、右で解きます.

[2] 73. Set Matrix Zeroes

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.
Follow up:

A straight forward solution using O(mn) space is probably a bad idea.

A simple improvement uses O(m + n) space, but still not the best solution.

Could you devise a constant space solution?

My Answer 1: Accepted (Runtime: 128 ms - 76.03% / Memory Usage: 14.9 MB - 98.48%)

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        R = len(matrix)
        C = len(matrix[0])
        
        rows = set()
        cols = set()
        
        for i in range(R):
            for j in range(C):
                if matrix[i][j] == 0:
                    rows.add(i)
                    cols.add(j)
        
        for r in rows:
            for j in range(C):
                matrix[r][j] = 0
        
        for c in cols:
            for i in range(R):
                matrix[i][c] = 0

最初はO(m + n)だと思って泣きそうになりましたがspace~
rows、colsというsetを作成し、ゼロのインデックス(r、c)のみを入れます.
そしてrowsとcolsに基づいてすべて0に設定します
これは…です.setはまた重複を解消することができて、O(mn) spaceではありませんて、いくらを知りません.

[3] 49. Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

My Answer 1: Error

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        
        for i in range(len(strs)):
            dic[collections.Counter(strs[i])] = strs[i]
        print(dic)
        
        result = []
        
        for val in dic.values:
            result.append(val)
        
        return result

最初はディックの鍵の値にディックの鍵を加えることができると思っていたが、それで終わりだった.{{'e':1 'a':1 't':1} : ['eat', 'tea']}こうして保存できると思っていたのに...

My Answer 2: Accepted (Runtime: 112 ms - 40.06%/ Memory Usage: 19.9 MB)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            dic[tuple(count)].append(s)
        
        return dic.values()

アスキーを計算するように...キー値としてcount tupleを使用する{(1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0) : ['eat', 'tea']}このように保存する
背負い直せ!!defaultdict=>dictionaryのサブクラス
初期値をcollections.defaultdict(list)=>(カッコ内)list値に設定

[4] 3. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

My Answer 1: Accepted (Runtime: 60 ms - 78.76% / Memory Usage: 14.2 MB - 94.27%)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
            
        cnt = 0
        start = -1
        
        for i in range(len(s)):
            if s[i] in dic and start < dic[s[i]]:
                start = dic[s[i]]
            dic[s[i]] = i
            cnt = max(cnt, i-start)
        
        return cnt

最初は、繰り返し値が発生するたびにdic値が初期化されます.
どうやって直接countするか考えていますが、効率が低すぎます.
したがって、初期インデックス=>startを使用する
dicに最新のインデックス値を追加します.print()に記入して提出すると出力制限になりますのでご注意ください

[5] 5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

My Answer 1: Wrong Answer (82 / 176 test cases passed.)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        
        maxstr = s[0]
        temp = ""
        
        for i in range(len(s)):
            if s[i] not in s[i+1:]:
                continue
            temp = s[i]
            for j in range(i+1, len(s)):
                if s[i] == s[j]:
                    if len(temp+s[i]) > len(maxstr):
                        maxstr = temp+s[i]
                temp += s[j]
        
        return maxstr

DICを使いたかったのですが出来ませんでしたほほほ
始まりと終わりが同じだからといって返事はしない...

Solution 1: Accepted (Runtime: 4232 ms - 26.15% / Memory Usage: 21.8 MB - 17.88%)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        # Form a bottom-up dp 2d array
        # dp[i][j] will be 'true' if the string from index i to j is a palindrome. 
        dp = [[False] * n  for _ in range(n)]
        
        ans = ''
        # every string with one character is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
            
        maxLen = 1
        for start in range(n-1, -1, -1):
            for end in range(start+1, n):             
                # palindrome condition
                if s[start] == s[end]:
                    # if it's a two char. string or if the remaining string is a palindrome too
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if maxLen < end - start + 1:
                            maxLen = end - start + 1
                            ans = s[start: end+ 1]
        
        return ans

n*n dpを作成し、他の文字と返信しているかどうかを確認します.start後ろから確認&end start右から確認if s[start] == s[end]:面の返信の最初の条件を満たすdp[start+1][end-1]が本当であれば、開始と終了の間の文字列も返信を表す.
=>Trueに設定してmaxLenとansを更新
全部暗記!!

[6] 334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

My Answer 1: Accepted (Runtime: 7340 ms - 5.04% / Memory Usage: 14.9 MB - 51.79%)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        for i in range(len(nums)):
            numJ = max(nums)
            for j in range(i+1, len(nums)):
                if numJ < nums[j]:
                    return True
                if nums[i] < nums[j]:
                    numJ = nums[j]
        
        return False

if nums[i] < nums[j]:でnumJが見つかりました.if numJ < nums[j]:検索値がnumJ=>Tripletより大きいのでTrueを返します.
でもO(n^2)だったのですごくスピードが遅くて…^^

My Answer 2: Accpeted (Runtime: 52 ms - 82.90% / Memory Usage: 14.7 MB - 80.26%)

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
        f_min = float('inf')
        s_min = float('inf')
        for i in range(len(nums)):
            if nums[i] <= f_min:
                f_min = nums[i]
            elif nums[i] <= s_min:
                s_min = nums[i]
            else:
                return True
        return False

ドア一つでいいf_min、s_minは異なる値を有し、値が2つの値(else:)より大きい場合、無条件に3元グループである
全部暗記!!
インデックスと辞書の使用率が高い
dpもぜひ知っておきたい!!