819. Most Common Word

Description

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words.  It is guaranteed there is at least one word that isn't banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation.  Words in the paragraph are not case sensitive.  The answer is in lowercase.

Example:
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

 

Note:

  • 1 <= paragraph.length <= 1000.
  • 1 <= banned.length <= 100.
  • 1 <= banned[i].length <= 10.
  • The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
  • paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
  • Different words in paragraph are always separated by a space.
  • There are no hyphens or hyphenated words.
  • Words only consist of letters, never apostrophes or other punctuation symbols.

 

Solution

Simple String processing

class Solution:
    def mostCommonWord(self, para, banned):
        banned = set(banned)
        # Only preserve a-z and space
        para = ''.join([_ if 'a'<=_<='z' or _==' ' else '' for _ in para.lower()])
        words = para.split()
        dic = collections.Counter(words)
        cnt, ret = 0, None
        for word in dic:
            if word not in banned:
                if dic[word]>cnt:
                    cnt = dic[word]
                    ret = word
        return ret

817. Linked List Components

Description

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

  • If N is the length of the linked list given by head1 <= N <= 10000.
  • The value of each node in the linked list will be in the range [0, N - 1].
  • 1 <= G.length <= 10000.
  • G is a subset of all values in the linked list.

Solution

Just count continuous nodes

class Solution:
    def numComponents(self, head, G):
        G = set(G)
        node = head
        cnt = 0
        while node:
            # If match, continue until not match
            if node.val in G:
                cnt += 1
                while node.next and node.next.val in G:
                    node = node.next
            node = node.next
        return cnt

818. Race Car

Description

Your car starts at position 0 and speed +1 on an infinite number line.  (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1.  (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.
Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

 

Note:

  • 1 <= target <= 10000.

Solution

Simple BFS, use a trick to prevent Memory Limit Exceed, only remember (position, speed) pair in visited when speed==1 or speed ==-1 (After R operation).

class Solution:
    def racecar(self, target):
        if target==0:
            return 0
        q = [(0, 1)]
        visited = set((0, 1))
        cnt = 0
        while q:
            new_q = []
            cnt += 1
            for pos, sp in q:
                p1, s1 = pos+sp, sp*2
                if p1==target:
                    return cnt
                p2, s2 = pos, -1 if sp>0 else 1
                
                # If we remember every position and speed pair, we get Memory Limit Exceed
                # The most annoying part is continuous R, so only remember situations with speed 1 and -1
                if (p1, s1) not in visited:
                    if s1==1 or s1==-1:
                        visited.add((p1, s1))
                    new_q.append((p1, s1))
                if (p2, s2) not in visited:
                    visited.add((p2, s2))
                    if s1==1 or s1==-1:
                        visited.add((p1, s1))
                    new_q.append((p2, s2))
            q = new_q
        return -1

816. Ambiguous Coordinates

Description

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)".  Then, we removed all commas, decimal points, and spaces, and ended up with the string S.  Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with less digits.  Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order.  Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]
Example 2:
Input: "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.
Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]
Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

 

Note:

  • 4 <= S.length <= 12.
  • S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits.

 

Solution

class Solution:
    def ambiguousCoordinates(self, S):
        
        def possible_val(S):
            ret = set()
            # S itself valid
            if S[0]!='0' or len(S)==1:
                ret.add(S)
            for _ in range(1, len(S)):
                left, right = S[:_], S[_:]
                # left of . valid if first char is not '0' or its length is just 1
                if len(left)==1 or not left[0]=='0':
                    # right of . valid if last char is not '0'
                    if right[-1]!='0':
                        ret.add(left+'.'+right)
            return ret
        
        # Remove parenthesis
        S = S[1:-1]
        ret = []
        for i in range(1, len(S)):
            # S1: String for first coord, S2: String for second coord
            S1, S2 = S[:i], S[i:]
            # Possible values for S1 and S2
            s1, s2 = possible_val(S1), possible_val(S2)
            if not s1 or not s2: continue
            for c1 in s1:
                for c2 in s2:
                    ret.append('('+c1+', '+c2+')')
        return ret