leetcode-98- Interleaving String

jackwang 發(fā)布于2019-07-31 11:03 / 683人閱讀

"""
97. Interleaving String
Description
HintsSubmissionsDiscussSolution
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

"""


class Solution:
    # BFS
    def isInterleave(self, s1, s2, s3):
        lx, ly, lz = len(s1), len(s2), len(s3)
        if lx + ly != lz:
            return False
        haved = [(0, 0)]
        visitedx = set()
        visitedy = set()
        while haved:
            x, y = haved.pop(0)
            if x + y == lz:
                return True
            # print(x,y)
            # if  x

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/44550.html

相關(guān)文章

leetcode97. Interleaving String

摘要：題目要求輸入數(shù)組和判斷是不是由和中的元素交替組成的。思路一乍一看這題可以通過遞歸的方式來求解。而走到和對(duì)應(yīng)的中的也是確定的。這里我們利用數(shù)組記錄判斷情況。所以我們可以將的二維數(shù)組簡化為一維數(shù)組的數(shù)據(jù)結(jié)構(gòu)。提高空間的利用率。題目要求 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2....

dmlllll 2019-08-15 10:58 評(píng)論0 收藏0
97 Interleaving String

摘要：和一樣給出和兩種方法。使用可以避免初始化的和結(jié)果的混淆。 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = aabcc, s2 = dbbca, When s3 = aadbbcbcac, return true. When s...

renweihub 2019-08-14 17:59 評(píng)論0 收藏0
[LintCode] Interleaving Positive and Negative Numb

摘要：注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計(jì)正數(shù)個(gè)數(shù)，若超過序列長度的一半，則正指針從開始，反之則負(fù)指針從開始。注意交換函數(shù)的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。 Problem Given an array with positive and negative integers. Re-range it to interleaving with positiv...

calx 2019-08-14 15:22 評(píng)論0 收藏0
【Leetcode】98. 驗(yàn)證二叉搜索樹

摘要：題目給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。所有左子樹和右子樹自身必須也是二叉搜索樹。題解這道題目主要是利用二叉搜索樹的一個(gè)性質(zhì)二叉搜索樹的中序遍歷結(jié)果是一個(gè)升序的序列。題目給定一個(gè)二叉樹，判斷其是否是一個(gè)有效的二叉搜索樹。假設(shè)一個(gè)二叉搜索樹具有如下特征：節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜...

nidaye 2019-08-16 15:10 評(píng)論0 收藏0
leetcode98. Validate Binary Search Tree

摘要：題目要求檢驗(yàn)二叉查找樹是否符合規(guī)則。二叉查找樹是指當(dāng)前節(jié)點(diǎn)左子樹上的值均比其小，右子樹上的值均比起大。因此在這里我們采用棧的方式實(shí)現(xiàn)中序遍歷，通過研究中序遍歷是否遞增來判斷二叉查找樹是否符合規(guī)則。題目要求 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is...

codercao 2019-08-15 10:56 評(píng)論0 收藏0