some interesting string problem

Find and Replace Pattern

You have a list of words and a pattern, and you want to know which words in words matches the pattern. A word matches the pattern if there exists a permutation of letters p so that after replacing every letter x in the pattern with p(x), we get the desired word. (Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.) Return a list of the words in words that match the given pattern. You may return the answer in any order.

Example Example 1: Input: words = [“abc”,“deq”,“mee”,“aqq”,“dkd”,“ccc”], pattern = “abb” Output: [“aqq”,“mee”] Explanation: “mee” matches the pattern because there is a permutation {a -> m, b -> e, …}. “ccc” does not match the pattern because {a -> c, b -> c, …} is not a permutation, since a and b map to the same letter. Example 2: Input: words = [“a”,“b”,“c”], pattern = “a” Output: [“a”,“b”,“c”] Explanation: All strings match.

Notice 1<=words.length<=50 1<=pattern.length=words[i].length<=20

class Solution:
    """
    @param words: word list
    @param pattern: pattern string
    @return: list of matching words
    """
    def findAndReplacePattern(self, words, pattern):
        # Write your code here.
        def F(w):
            m = {}
            return [m.setdefault(c, len(m)) for c in w]
        Fp = F(pattern)
        #print(Fp)
        return [w for w in words if F(w) == Fp]

Flip String to Monotone Increasing

A string of ‘0’s and ‘1’s is monotone increasing if it consists of some number of ‘0’s (possibly 0), followed by some number of ‘1’s (also possibly 0.) We are given a string S of ‘0’s and ‘1’s, and we may flip any ‘0’ to a ‘1’ or a ‘1’ to a ‘0’. Return the minimum number of flips to make S monotone increasing.

Example Example 1: Input: “00110” Output: 1 Explanation: We flip the last digit to get 00111. Example 2: Input: “010110” Output: 2 Explanation: We flip to get 011111, or alternatively 000111.

Notice 1≤S.length≤20000 S only consists of ‘0’ and ‘1’ characters.

class Solution:
    """
    @param S: a string
    @return: the minimum number
    """
    def minFlipsMonoIncr(self, S):
        # start with assuming all 1 ,that is to say, '111'
        # then we iterate S and update S[:i+1] to '000...' section and S[i+1:] to '111...' section 
        # zero_num counts all misplaced 0s and one_num counts all misplaced 1s
        zero_num = S.count('0')
        one_num = 0
        ans = float('inf')
        for c in S:
            if c == '1':
                one_num += 1
            else:
                zero_num -= 1
            ans = min(ans,one_num+zero_num)
        return ans

Tags

• Algorithm