[Lintcode Ladder2] String

阅读量：4686 次

发布时间：2019-06-09

本文共 5305 字，大约阅读时间需要 17 分钟。

1.

Description

Write a method anagram(s,t) to decide if two strings are anagrams or not.

Have you met this question in a real interview?

Clarification

What is Anagram?

Two strings are anagram if they can be the same after change the order of characters.

Example

Given s = “abcd”, t = “dcab”, return true.

Given s = “ab”, t = “ab”, return true.

Given s = “ab”, t = “ac”, return false.

Challenge

O(n) time, O(1) extra space

我的代码：

class Solution:    def getdic(self, s):        d_s = {
    }        for key in s:            d_s[key] = d_s.get(key,0)+1        return d_s    def isAnagram(self, s, t):        """        :type s: str        :type t: str        :rtype: bool        """        return self.getdic(s) == self.getdic(t)

其他人的代码：

def isAnagram3(self, s, t):    return sorted(s) == sorted(t)

注意：此时得到的是一个数组

思路：

我想的是，如果顺序不重要的话，就是相应的字母都有，而且数量一样。所以可以用dictionary来实现（数组亦可）。看到一行代码的思路是顺序不重要的话，可以按照相同的规则重新排序，最后结果完全一样就可以了。

2.

Description

Compare two strings A and B, determine whether A contains all of the characters in B.

The characters in string A and B are all Upper Case letters.

The characters of B in A are not necessary continuous or ordered.

Have you met this question in a real interview?

Example

For A = “ABCD”, B = “ACD”, return true.

For A = “ABCD”, B = “AABC”, return false.

我的代码：

def compareStrings(self, A, B):        # write your code here        dic_A = {
    }        for key in A:            dic_A[key] = dic_A.get(key,0)+1        dic_B = {
    }        for key in B:            dic_B[key] = dic_B.get(key,0)+1        for keyb in B:            if dic_A.get(keyb) == None:                return False            else:                if dic_A.get(keyb) < dic_B[keyb]:                     return False        return True

思路：

大抵同上一题

3.

Description

For a given source string and a target string, you should output the first index(from 0) of target string in source string.

If target does not exist in source, just return -1.

Have you met this question in a real interview?

Clarification

Do I need to implement KMP Algorithm in a real interview?

Not necessary. When you meet this problem in a real interview, the interviewer may just want to test your basic implementation ability. But make sure you confirm with the interviewer first.

Example

If source = “source” and target = “target”, return -1.

If source = “abcdabcdefg” and target = “bcd”, return 1.

Challenge

O(n2) is acceptable. Can you implement an O(n) algorithm? (hint: KMP)

我的代码

暴力求解

def strStr(self, source, target):        # Write your code here        h = 0        t = 0        l_s = len(source)        l_t = len(target)        if source == target:            return 0        for i in range(l_s-l_t+1):            if source[i:i+l_t] == target:                return i        return -1

学习 KMP

参考文章：

该算法的重点是，构建一个部分匹配表，使得无法完整匹配时，不是单步移动，而是移动最长的前缀后缀匹配位置。

#KMP# s 原字符串# p 子串def kmp_match(s, p):    m = len(s); n = len(p)    cur = 0#起始指针cur    table = partial_table(p)    while cur<=m-n:        for i in range(n):            if s[i+cur]!=p[i]:                cur += max(i - table[i-1], 1)#有了部分匹配表,我们不只是单纯的1位1位往右移,可以一次移动多位                break        else:            return True    return False #部分匹配表def partial_table(p):    '''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''    prefix = set()    postfix = set()    ret = [0]    for i in range(1,len(p)):        prefix.add(p[:i])        postfix = {
    p[j:i+1] for j in range(1,i+1)}        ret.append(len((prefix&postfix or {
    ''}).pop()))    return retprint kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")

4.

Description

Given an array of strings, return all groups of strings that are anagrams.

All inputs will be in lower-case

Have you met this question in a real interview?

Example

Given [“lint”, “intl”, “inlt”, “code”], return [“lint”, “inlt”, “intl”].

Given [“ab”, “ba”, “cd”, “dc”, “e”], return [“ab”, “ba”, “cd”, “dc”].

Challenge

What is Anagram?

Two strings are anagram if they can be the same after change the order of characters.

我的代码：

class Solution:    """    @param strs: A list of strings    @return: A list of strings    """    def anagrams(self, strs):    # write your code here        dic = {
    }        #将字符按照字母表顺序，重新排序，作为它的anagram特征        for item in strs:            item_ = ''            for i in sorted(item):                item_ += i            dic[item_] = dic.get(item_, 0) + 1        res = []        for item in strs:            item_ = ''            for i in sorted(item):                item_ += i            #若特征相同，则为anagram            if dic[item_] > 1:                res.append(item)        return res

78. Longest Common Prefix

Description

Given k strings, find the longest common prefix (LCP).

Example

For strings “ABCD”, “ABEF” and “ACEF”, the LCP is “A”

For strings “ABCDEFG”, “ABCEFG” and “ABCEFA”, the LCP is “ABC”

我的代码

class Solution:    """    @param strs: A list of strings    @return: The longest common prefix    """    def longestCommonPrefix(self, strs):        if strs == []:            return ""        l = max([len(i) for i in strs])        res = ""        for i in range(0,l):            if len(set([prefix[:i+1] for prefix in strs])) == 1:                res = strs[0][:i+1]        return res