LeetCode开心刷题二十三天——43Multiply Strings 44. Wildcard Matching

淡淡的烟草味﹌ 2023-08-17 15:14 83阅读 0赞

43. Multiply Strings

Medium

1069486FavoriteShare

Given two non-negative integers `num1` and `num2` represented as strings, return the product of `num1` and `num2`, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
    Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
    Output: "56088"

Note:

1.  The length of both `num1` and `num2` is < 110.
2.  Both `num1` and `num2` contain only digits `0-9`.
3.  Both `num1` and `num2` do not contain any leading zero, except the number 0 itself.
4.  You must not use any built-in BigInteger library or convert the inputs to integer directly.

addedbonus：

1.initialize：string length l1+l2,all 0;

stringans(l1\+l2,'0');

2.We should be aware of this when we dealing with string problems.

the number we use isn't 0,1,2.....but '0','1','2','3'....clarify the difference between0 and '0';During our calculation,we always

forget to add '0' when we deal with transfer through string and number,so pay attention please!

3.In this problem,the output has to be sth.a number or zero.so if when we get through the answer but find it has been the

last one but it also 0,we have to output it.So the output judge condition is if nums\[i\]!=0||i=ans.length()-1

#include<iostream>
    #include<string>
    #include<stdio.h>
    #include<string.h>
    #include<iomanip>
    #include<vector>
    #include<list>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<map>
    using namespace std;
    class Solution {
    public:
        string multiply(string num1, string num2) {
            const int l1=num1.size(),l2=num2.size();
            string ans(l1+l2,'0');
            for(int j=l2-1;j>=0;j--)
            {
                for(int i=l1-1;i>=0;i--)
                {
    //                cout<<num1[i]-'0'<<endl;
    //                cout<<num2[j]-'0'<<endl;
    //                cout<<ans[i+j+1]<<endl;
                    int temp=(ans[i+j+1]-'0')+(num1[i]-'0')*(num2[j]-'0');
    //                cout<<temp<<":"<<endl;
                    ans[i+j+1]=temp%10+'0';
                    ans[i+j]+=temp/10;
                }
            }
    //        for(int i=0;i<l1+l2;i++)
    //        {
    //            cout<<"ans"<<i<<":"<<ans[i]<<endl;
    //        }
            for(int i=0;i<l1+l2;i++)
            {
                if(ans[i]!='0'||i==ans.length()-1)
                    return ans.substr(i);
            }
            return "";
        }
    };
    int main()
    {
        Solution s;
        string res;
        string num1="2",num2="2";
        res=s.multiply(num1,num2);
        cout<<res<<endl;
        return 0;
    }

Python的int可以无限大的，所以没有真正实现了大数乘法。

python do really well in some aspects.

Python Version：Knowledge

1、Python中的//应该是向下取整的意思  
a//b，应该是对a除以b的结果向负无穷方向取整后的数  
5//2=2（2.5向负无穷方向取整为2），同时-5//2=-3（-2.5向负无穷方向取整为-3）

Because in python the type of variable not be clarified by code,so if we let variable=a/b,maybe this value would be

double so we need use // to let this value is int.

2.enumerate is like iterator.

3.ord() use to show the value of character,such as a ->96

4.num\[::-1\] means tranverse

5. \*\* represent

>>> –3\*\*2 \# 需要注意幂运算的优先级比-号取反的优先级要高  
\-9 \# 如果想表示(-3)\*\*2 需要用括号括起来  
>>> pow(3, 2)  
9

python version website:

[https://blog.csdn.net/fuxuemingzhu/article/details/80681702][https_blog.csdn.net_fuxuemingzhu_article_details_80681702]

In fact,python version a little bit hard to understand,especially the \*\* part,Need to repeat look again.

class Solution(object):
        def multiply(self, num1, num2):
            if num1=='0' or num2=='0':
                return '0'
            ans=0
            for i,n1 in enumerate(num2[::-1]):
                pre=0
                curr=0
                for j,n2 in enumerate(num1[::-1]):
                    multi=(ord(n1)-ord('0'))*(ord(n2)-ord('0'))
                    first,second=multi//10,multi%10
                    curr+=(second+pre)*(10**j)
                    pre=first
                curr+=pre*(10**len(num1))
                ans+=curr*(10**i)
            return str(ans)
    
    if __name__ == '__main__':
        num1="84"
        num2="6"
        solu = Solution()
        print(solu.multiply(num1,num2))

44. Wildcard Matching

Hard

114877FavoriteShare

Given an input string (`s`) and a pattern (`p`), implement wildcard pattern matching with support for `'?'` and `'*'`.

'?' Matches any single character.
    '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

*  `s` could be empty and contains only lowercase letters `a-z`.
 *  `p` could be empty and contains only lowercase letters `a-z`, and characters like `?` or `*`.

Example 1:

Input:
    s = "aa"
    p = "a"
    Output: false
    Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
    s = "aa"
    p = "*"
    Output: true
    Explanation: '*' matches any sequence.

Example 3:

Input:
    s = "cb"
    p = "?a"
    Output: false
    Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
    s = "adceb"
    p = "*a*b"
    Output: true
    Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".

Example 5:

Input:
    s = "acdcb"
    p = "a*c?b"
    Output: false
    
    bonus：
    Ctrl+/ multiline comment
    array in python can be print directly,print(cache) then cache array will be showed 
    directly.
    False & false are different in python
    range(1,x)or range(x) always only transverse to x-1
    Every time you handle the problem,Special case solving is the first thing
    recommend a function count.can calculate the number in the string.
    The most outstanding merit of this python solution is use scroll the array,largely lower
    the space requirements from 1000*1000 to 2*1000
    python version:

#special space store is helpful,less 1000*1000 to 2*1000,use array to store the value
    #the value only we need is the left-down one,the regular is only if we know top,left,
    #and top-left we can get the value,so if we want the last-right value just know two rows is ok
    class Solution(object):
        def isMatch(self,s,p):
            #special case very important please don't forget next time
            if len(p)-p.count('*')>len(s): return False
            cache=[[False for i in range(len(s)+1)]for j in range(2)]
            cache[0][0]=True
            for i in range(1,len(p)+1):
                cache[i%2][0]=cache[(i-1)%2][0] and p[i-1]=='*'
                for j in range(1,len(s)+1):
                    cache[i%2][j]=False
                    print(i,j)
                    if (s[j-1]==p[i-1]) or (s[j-1]=='?') or (p[i-1]=='?'):
                        cache[i%2][j]=cache[(i-1)%2][j-1]
                    if (s[j-1]=='*') or (p[i-1]=='*'):
                        cache[i%2][j]=cache[i%2][j-1] or cache[(i-1)%2][j]
            print(cache)
            return cache[len(p)%2][len(s)]
    
    #actually don't need main function
    #__name__ == '__main__':
    a="a"
    #attention same symbol write in English and Chinese are different
    b="?"
    #don't forget () very important
    solu=Solution()
    print(solu.isMatch(a,b))

C++ version:
    These two are totally different thoughts.Python wants to store the result and calc
    result by rely on the top-left part.So it need array to store.But C++ just judge and calc
    It use traceback if we face to * we assume it is empty,if we cannot finish it then we
    come back to the latest point of *.Because of the advantages of the algorithm itself
    C++ faster than python

#include<stdio.h>
    #include<iostream>
    #include<string>
    using namespace std;
    class Solution
    {
    public:
        bool isMatch(string& s, string& p)
        {
            bool res=0;
            const int s1=s.size(),p1=p.size();
    
            int si=0,pi=0;
            int sStarIndex=-1,pStarIndex=-1;
            while(si<s1)
            {
                if(s[si]==p[pi]||p[pi]=='?')
                {
                    si++;
                    pi++;
                }
                else if(p[pi]=='*')
                {
                    sStarIndex=si;
                    pStarIndex=pi++;
                }
                else if(sStarIndex>-1)
                {
                    si=++sStarIndex;
                    pi=pStarIndex+1;
                }
                else return false;
            }
            while((pi<p1)&&(p[pi]=='*')) pi++;
            if(pi!=p1) return false;
            return true;
        }
    };
    int main()
    {
        Solution s;
        bool res=false;
        string s1="abc",s2="a*v";
        res=s.isMatch(s1,s2);
        cout<<res<<endl;
        return 0;
    }

转载于:https://www.cnblogs.com/Marigolci/p/11221642.html

[https_blog.csdn.net_fuxuemingzhu_article_details_80681702]: https://blog.csdn.net/fuxuemingzhu/article/details/80681702