Leetcode 17: Letter Combinations of a phone number (DFS)

January 24, 2016
 
17 Letter Combinations of a phone number (DFS)

Julia likes to focus on basic things about algorithms, she tries to focus on recursive function design, BFS, DFS, backtracking. Here is her favorite DFS algorithm, she tries to build more fun memory about DFS algorithm, every time she works on DFS algorithm, she is so happy and eager to share her 2 cents, learned from Leetcode blogs - all her favorite blogs.

http://www.cnblogs.com/grandyang/p/4452220.html
Analysis from the above blog:
这道题让我们求电话号码的字母组合，即数字2到9中每个数字可以代表若干个字母，然后给一串数字，求出所有可能的组合，相类似的题目有 Path Sum II 二叉树路径之和之二，Subsets II 子集合之二，Permutations 全排列，Permutations II 全排列之二，Combinations 组合项， Combination Sum 组合之和和 Combination Sum II 组合之和之二等等。我们用递归Recursion来解，我们需要建立一个字典，用来保存每个数字所代表的字符串，然后我们还需要一个变量level，记录当前生成的字符串的字符个数，实现套路和上述那些题十分类似，

Her practice is too weak in 2015.
https://github.com/jianminchen/Leetcode_C-/blob/master/LetterCombinationOfAPhoneNumber.cs

Missing in the last practice:
1. Use iterative solution, but lack of analysis - (comment area, hard to review)
2. Should focus on DFS solution, basic things.

New practice in January 2016:
1. using recursive to solve the problem, it is fast and quick way to solve it in 10 minutes.
2. Only need to write a few lines of code.
3. Need to design recursive function.
4. Need to do backtracking,
5, Need to do char, string, int a few types, and also do type conversion.

Julia's practice, it took her 27 minutes to write down, compile, and have some comment written.
https://github.com/jianminchen/Leetcode_C-/blob/master/17LetterCombinationOfAPhoneNUmber_DFS.cs

January 24, Read more blogs on this question:

和subset, combination问题一样的backtracking。唯一的区别是要先建立一个从数字到字母的转换表。这样每一层递归遍历当前digits[i]所对应的所有字母，并加入当前combination中传到下一层递归。
Iterative solution: 这里需要克隆多份之前的解集。
http://bangbingsyb.blogspot.ca/2014/11/leetcode-letter-combinations-of-phone.html

Java, using hashmap - Good idea
http://blog.welkinlan.com/2015/10/25/letter-combinations-of-a-phone-number-leetcode-java/

终于出现我最不擅长的递归题了，这道题是经典递归题，标准DFS解法，应作为模板牢牢记住。
http://simpleandstupid.com/2014/10/16/letter-combinations-of-a-phone-number-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

So, Julia is not good at recursive function design as well. So, she likes to search a blog and find the most important tip she can grasp in next 20 minutes.

Array initiliazation can be in one line instead of more than 8 lines
http://yucoding.blogspot.ca/2013/01/leetcode-question-42-letter.html

DFS, backtracking is clear in the code.
http://rleetcode.blogspot.ca/2014/02/letter-combinations-of-phone-number-java.html

Java code, member of class - hashmap - static - first time read static - declare variables sharing static in statement. (missing backtracking? or does not matter)
https://github.com/rffffffff007/leetcode/blob/master/Letter%20Combinations%20of%20a%20Phone%20Number.java

very well written,
http://codesniper.blogspot.ca/2015/01/17-letter-combinations-of-phone-number.html

using vector instead of hashmap
http://yumei165.blogspot.ca/2013/04/letter-combinations-of-phone-number-c.html

Good analysis - read the analysis in the following blog -

• 这个是一个结果是排列组合的问题,一个类似的问题就是小组赛N个队, 相互之间的比赛 列表. 这种问题就是回溯法
• 回溯法最重要的就是要"先加再减" (Julia's comment -> backtracking ) 
• 回溯法函数参数的设计是把结果当成参数(此处是用参数引用), 返回值返回一个void. 这样容易设计递归.
• java的做法会比c++看起来麻烦一点, 而且java是无法做到真的const String数组

http://harrifeng.github.io/algo/leetcode/letter-combinations-of-a-phone-number.html

九章算法
http://www.jiuzhang.com//solutions/letter-combinations-of-a-phone-number/

Analysis from the following blog:
Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 
http://buttercola.blogspot.ca/2014/09/leetcode-letter-combinations-of-phone.html

use this one as my example to write a good solution. Good style!
https://segmentfault.com/a/1190000003766442

Excellent code style.
http://shanjiaxin.blogspot.ca/2014/02/letter-combinations-of-phone-number.html

So, put together something for DFS /backtracking algorithm - favorite tips:
1. DFS, do not forget backtracking, using Chinese words, "先加再减". 
2. Recursive function design:
    Return result C#: IList<string>, 
    put it as input argument or member variable of class Solution 
3. Remember a tip to convert a char to int, very basic convert using this: 
    Char c (no one can remember the ascii value of '0', but use type conversion c-'0', char to int; in other words, compare to relative char, get the value by type conversion automatically).
    c - '0' 

4. dictionary declaration, common and easy way is to declare one dimension array:

    String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

5. using C# or Java, string class is not good, using StringBuilder class instead. 

6. Remember one or two DFS algorithms, use them to relax and help to figure out design issue, difficulty level of DFS problem solving - honestly, it is easy and quick solution, less time-consuming compared to an iterative solution, more time-consuming DP with memorization solution. 
   

Suffix Rotation - a test case tells the truth

January 17, 2017

Introduction

Julia had some study on Leetcode 17 - a phone number algorithm, one of studies is on stack/ queue implementation of the algorithm in May 2016. After more than 6 months, in January 2017, she worked on suffix rotation algorithm in the contest, she made a mistake to choose using queue instead of stack.

So, after the week code 28 contest, in 1 - 2 day, she studied suffix rotation's test case provided by hackerrank: a string "lcatqjejhpgkrkhnxsfyqlulncefeytykwnqbfmqaduldwhgwruwkdvojexefcmfrlfuzzcurjgnnbkskbzw", the code has issues related to out-of-memory, queue size is over 11,387,997, 10 millions, stop after processing first 12 chars "aaabbbbbccc", over one minute at least.

code with bugs is here.

Suffix Rotation C# practice, with a bug running out of memory.

working code is here.

Problem Solving 

Thank you, a small test case helps me to understand the issue again. Queue vs Stack, for phone number less than 7 digits, queue is still ok - not causing out-of-memory issue. But with string with length over 20, the problem quickly comes out easily.

lcatqjejhpgkrkhnxsfyqlulncefeytykwnqbfmqaduldwhgwruwkdvojexefcmfrlfuzzcurjgnnbkskbzw

Remember this test case, as a programmer, Julia has to work on a test case more often; build a good habit to figure out issues in the design with help of test cases, specially in any hackerrank contest. Kind of boring talk, let us talk about a song.

The solid Rock, corner stone or sinking sand

Julia has a favorite song she likes to sing along a lot of times, specially a lot of years ago (2000 - 2010) in Boca Raton

community church - My hope is built on nothing less.

Related to being a hackerrank contest player, Julia has some hope, the test case can be her solid rock if she has weakness in the design, and flaws in thinking process.

The test case is the solid Rock, I stand;

All other ground is sinking sand, 

All other ground is sinking sand.

Code review study

Julia chooses to study more on phone number related algorithms.

1. Code review: Phone number.

2. Very good Dynamic programming explanation, read the phone number's code review by Google engineer.

3. Phone number code review - group of 3 digits with no lone digits.

4.    Print all permutations with some constraints

5.    Reversing words in a string

6.    Function to compare phone numbers

7.    Let me fix thou number

At last, review algorithm code review made by a google engineer, click here.

Microsoft Teams | How to use Skype phone number?

 Yes, Microsoft Teams can utilize Skype phone numbers, specifically Skype Numbers, in a few ways, but it requires a Teams Phone license and potentially a Calling Plan. Skype for Business, which is a separate product, is being retired and users are encouraged to migrate to Microsoft Teams. 

Here's a more detailed explanation:

• Skype Numbers in Teams:

  If you have a Skype Number (a phone number you purchased through Skype), you can port it to Microsoft Teams. This allows you to receive calls on that number within the Teams environment. 
• Teams Phone License:

  To use Skype Numbers or any other phone number for calls within Teams (including making calls to regular phones), you need a Teams Phone license. 
• Calling Plans:

  If you want to make calls from Teams to regular phones (landlines and mobile phones), you'll also need a Calling Plan, which is an add-on to the Teams Phone license. 
• Migration from Skype for Business:

  If you were using Skype for Business, you can port your Skype for Business number to Teams. Microsoft has provided resources and guidance to help users migrate their Skype for Business data and settings to Teams. 
• Skype Dial Pad in Teams Free:

  If you're using Microsoft Teams Free, you can access a Skype Dial Pad to make calls if you have active Skype Credit or a subscription. 

 

WeChat Enables Foreigners to Pay with Overseas Cards in China

July 24, 2023Posted by China BriefingWritten by Giulia InteresseReading Time:  6 minutes

Tencent’s latest WeChat Pay upgrade enables foreign users to link international cards, enhancing mobile payments in China and aligning with efforts to attract international tourists and boost domestic consumption.

---

On July 20, 2023, Tencent, in collaboration with leading international financial services providers like Visa, Discover Global Network, JCB, and Mastercard announced significant improvements to the mobile payment experience for foreign users in China.

Tencent has expanded the WeChat Pay merchant network across multiple cities in China, providing support to merchants in various sectors, including dining, transportation, retail, and hospitality. This development will facilitate diverse payment methods like QR code scanning, in-app purchases, and WeChat Mini Programs, offering added convenience to users.

WeChat Pay had already allowed international credit card binding since 2019 and conducted trials with select merchants in essential sectors. With this recent development, inbound travelers, including those with passports and various permits, can now easily utilize WeChat Pay and link their international bank cards to make purchases at millions of merchants.

Moreover, to enhance the payment experience for users making frequent small transactions, WeChat Pay will bear the transaction fees for international card transactions below RMB 200 (US$27.82), providing users with fee exemptions during payment.

This move by Tencent aligns with the plans previously released by the State Council and the National Development and Reform Commission, aimed at improving mobile payment solutions for inbound tourists and increasing their convenience in making payments ahead of major international events, such as the 2022 Beijing Olympic Winter Games. At that time, the authorities encouraged domestic payment service providers to collaborate with overseas card issuers within legal and regulatory frameworks to offer mobile payment services to foreign visitors.

With China hosting various international events in 2023, such as the Chengdu FISU World University Games and the Hangzhou Asian Games, the number of inbound visitors is expected to rise. Tencent’s expansion of the WeChat Pay merchant network will significantly enhance the mobile payment experience for foreign users, further promoting China as a preferred destination for international travelers.

Below we delve into how foreign users can make payments via WeChat Pay. We provide comprehensive details on the process, timing, and relevant sources for further information.

How can foreign users make payments in China via WeChat?

Foreign users can make payments via WeChat by linking their international credit or debit cards to the WeChat Pay platform. After entering the Chinese mainland, foreign visitors can easily set up WeChat Pay on their WeChat app and proceed to add their international cards issued by Visa, Mastercard, JCB, or Discover Global Network.

Once the cards are successfully linked, foreign users can use WeChat Pay to make payments to merchants across various sectors, including dining, shopping, transportation, and hotel accommodation.

This convenient and seamless payment method enables foreign users to “pay like a local” in China, without the need to carry cash or open a Chinese bank account.

What documents are required for setting up WeChat Pay?

Currently, six types of documents can be used to open a WeChat Pay account. These are:

• Passport
• Foreign Permanent Resident ID Card
• Mainland Travel Permit for Hong Kong and Macao Residents
• Mainland Travel Permit for Taiwan Residents
• Residence Permit for Hong Kong and Macao Residents
• Residence Permit for Taiwan Residents

These documents are all accepted for the registration process of WeChat Pay.

How to bind foreign cards to WeChat Pay?

To bind their foreign cards to WeChat Pay, users can follow these simple steps:

• Make sure the app is updated to its latest version.
• Open WeChat and go to the “Me” section.
• Tap on “Wallet” to access your payment options.
• Click on “Bank Card” and choose “Add a New Bank Card.”
• Enter the card number, select the type of card, and the issuing organization. Fill in the required card and personal information.
• Once everything is filled out, click “Submit.” A confirmation message will appear when the binding is successful.

After the verification, an SMS verification code will be sent to the phone number provided earlier. Enter the code to complete the verification process.

During the card binding process, the mobile phone number needed for verification should be capable of receiving SMS verification codes. Importantly, this number does not have to be a mobile phone number from mainland China, but it can also be a foreign number.

Finally, create a 6-digit payment password to ensure the security of your WeChat Pay account. Once these steps are completed, users can start using WeChat Pay with their foreign card for various transactions at millions of merchants, making payments in China as convenient as possible.

Google makes business call easy

Google makes calling businesses less painful with features for seeing wait times, phone tree options and more 

Sarah Perez@sarahintampa / 1:30 PM PDT•October 19, 2021

Alongside today’s release of the new Pixel 6 smartphones, Google has again upgraded one of the device’s most basic — but often overlooked — functions: the ability to make phone calls. In previous years, Google Assistant learned to screen your calls and make your reservations by phone via a technology called Duplex. Last year, it learned how to wait on hold for you, too. Today, Google is expanding some of these existing features and adding new ones — including a tool that shows you the best time to call a business and a new Duplex-powered feature for navigating businesses’ phone trees.

With the Phone app on Pixel 6 and Pixel 6 Pro, a new feature called “Wait Times” will display the projected time it will take to get through to a person when dialing a toll-free number. You’ll be able to see this information before you place the call not only for the present time, but also for the rest of the week. This information may allow you to make a better decision about when to place the call.

Of course, in order to show this information, Google is leveraging its ability to collect data from its users. Similar to how Google Maps will show you when a business is the most crowded using anonymized data from Maps users, “Wait Times” are inferred from call length data when calls are placed through its phone app. This data is not linked to individual users, Google says.

Another new addition is the “Direct My Call” feature, which will help you get through complicated phone trees when you dial a business. Instead of listening and trying to remember the many options presented (e.g., “Press 1 for hours and locations”), Google Assistant will translate the automated messages for you. This allows you to read back through the options to see which number you’ll want to tap to get the information you need — or to reach a live agent, as is often the case.

In the past, users frustrated with difficult customer service calls may have turned to third-party apps and websites like GetHuman, to figure out how to reach a real person more quickly. But these websites aren’t always up to date. “Direct My Call” offers an alternative. You could multitask or even set your phone down while the various options are read aloud — something that’s tedious to have to listen to in real time. When you return to the phone, you’ll be able to read the options available and choose the one you need. (The feature could also help those who are hard of hearing, but who don’t yet require a TTY.)

Like the the earlier reservation-setting feature, “Direct My Call” is also powered by Google Duplex technology.

Duplex is sometimes confused with the reservation scheduling feature itself, which was one of the first big use cases for the technology when it debuted. But Duplex itself doesn’t just enable natural-sounding conversations for making your appointments. It can be used for understanding, too. In the case of “Direct My Call,” for example, Duplex uses advanced speech recognition and language understanding models to help determine when the business wants you to do something — like press a number, say a word (like “representative”) or enter your account number, among other things.

In addition to “Direct My Call” and “Wait Times,” which are launching with the Pixel devices, for the time being, Google is also expanding access to “Hold for Me.”

Since launching last year in the U.S., the feature has saved users over 1.5 million minutes per month. In the coming months, it will begin to roll out to Pixel users in Australia, Canada and Japan, as well, says Google. 

Meanwhile, Google’s existing call screening functions are also getting an upgrade.

Before, Google’s own caller ID coverage would help users to identify spam and other calls from unknown numbers. Now, it will allow users to contribute data about their incoming business calls, too. That means you’ll be able to share what type of business had called you (e.g., bill collectors, finance, utilities, etc.) so that others who receive the same call in the future will know what to expect. This data is shared without any personal identifiers, notes Google. The company believes this will help double the number of businesses with caller ID information going forward.

In addition, call screening will expand to more markets. In the U.S., Canada and Japan, it’s now screening 37 million calls per month. Starting today, it will roll out to Pixel users in the U.K., France, Germany, Australia, Ireland, Italy and Spain, too.

Typically, Google releases new features to its latest Pixel phones first, before rolling them out over time to more Pixel devices or Android more broadly. That means “Wait Times” and “Direct My Call” will likely be exclusive to Pixel 6 phones for some time, initially.

Leetcode discuss: 84. Largest Rectangle in Histogram

Here is my post.

C# review my second practice in August 2018

June 28, 2020

Introduction

I only have two more weeks to prepare Facebook July phone screen. I came cross this algorithm, and I found my practice back in 2018. I found my blogs to document the experience, and I like to write a post to share my learning as well.

January 18, 2018 My blog about Leetcode 84. Here is the blog.
April 10, 2018, here is the blog.
August 5, 2018, here is the blog.

Case study

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
For example, [2, 1, 5, 6, 2, 3]
largest histogram is 5 + 5 = 10

Brute force solution, choose all pair of start and end position, and then calculate the area and keep maximum.

Next, consider how to remove redundant work.
First of all, play with as many simple test cases first, and then try to find ideas to solve the problem.
[3, 2], the answer is 4.
Let us talk about this example, there are three cases to consider, [3], [2, 2], and [2] is skipped since 2 < 3. Make sure that area width 1 and 2 both are considered in comparison.

[5], the answer is 5.
[5, 3], the answer is 6.
[5, 2], the answer is 5.
[1, 5], the answer is 5.

how about [3, 2, 1]?
There are [3], [2, 2], [1, 1, 1], so the maximum one will be 4. First, 3 < 4, so [2, 2]'s area is larger than [3].

[2, 3], the answer is 4.
ascending, how to calculate area and get maximum one is 4.
[2, 3, 4], the answer is to find Math.Max{4, 3 * 2, 2 * 3} = 6. If I enumerate all possible rectangles, three are three areas with one number, two areas with two numbers, one area with three numbers.
We can argue that three areas with one number can be simplified, only check last number since it is largest one.
We also can argue that two areas with two numbers can be simplified, only check last two numbers in ascending order numbers, since rightmost one is largest one.
Based on the test case [2, 3] and [2, 3, 4], we can argue that putting all ascending numbers into stack first, once it goes down, then pop up each number in the stack, and then calculate the maximum one.

test case: [3, 4, 3, 4], maximum area is 12.
How to get the area is 12?
Let me reason one step a time.
First put [3] into stack;
Next 4, 4 > 3, so put 4 into stack; stack: [3, 4];
Next 3, so 3 < peek of top of stack 4, pop 4, calculate area with one number, [4], value should be 4; update max = 4; (why not consider 3? Since 3 < 4, no need to calculate area width 1 with a smaller value, starting from 4.)
continue to compare top of stack, 3 == 3, pop 3, calculate the area with three numbers [3, 4], so the total is 3 * 2 = 6;
Next 4, so put 4 into stack; stack [3, 4];
Now all numbers are visited in the array, pop 4, area is 4 < max = 6;
Pop 3, the stack is empty, in other words, 3 is the minimum number of all numbers in the array, termination case, 3 * length of the array = 3 * 4 = 12, which is bigger than max = 9, so max = 12.

Let me repeat the idea to solve [3, 4, 3, 4]. The idea is to cover all possible areas with different lengths, remove redundant ones if possible. So one of tasks is to find the minimum number in the array, and then area including all numbers span of width will be calculated, the area will be compared with maximum area.

How to find the minimum number of the array? When to remove numbers bigger than minimum number when going through the array iteration one by one?

Breakthrough
Go over test case [3, 4, 3, 4] and explain to myself how to find maximum area 12.
First keep a stack in ascending order, and then first two numbers into stack [3, 4], and the third number is 3, then remove numbers in the stack bigger than 3, and also calculate the area with one number, two numbers, three numbers, ...
Make sure that last number in the stack should be minimum number in the array, all numbers span will be counted to the area with minimum number, which is 12.

In detail, only the following areas are calculated and compared, [4], [3, 4], [4], [3], index value in the stack, so [1], [0, 1], [3], [2], the width calculation is challenge one for special case, last number in the stack.

The following diagram is copied from the blog I wrote in 2018.

I will write down step by step how to work on the example, calculate the area of largest rectangle in the histogram.

I will add more review later. Stay tuned.

Problems in my practice back in 2018
I do not understand the power of case study. I need to write down a challenge test case, and then step by step explain to myself how to solve the problem? How to improve using stack data structure? What is most challenging part in the design.

I do think that [3, 4, 3, 4] is a good test case for me to remember to solve the problem. Go over the steps to find maximum area 12.

public class Solution {
    public int LargestRectangleArea(int[] height) {
            var stack = new Stack<int>();

            var index = 0;
            var largestArea = 0;

            int length = height.Length; // 6

            while (index < length) // true; index = 1; index = 2;
            { 
                //     stack empty            going upward
                if (stack.Count == 0 || height[stack.Peek()] < height[index]) // index = 1, false;
                {
                    stack.Push(index++); // 0, index = 1;
                }
                else
                {
                    // going downward and then pop stack, calculate rectangle.
                    popStackAndCalculate(ref largestArea, stack, height, index);
                }
            }

            while (stack.Count > 0)
            {
                popStackAndCalculate(ref largestArea, stack, height, length);
            }

            return largestArea;
        }

        /// <summary>
        /// downward and then pop stack to calculate the rectangle
        /// </summary>
        /// <param name="largestArea"></param>
        /// <param name="stack"></param>
        /// <param name="height"></param>
        private static void popStackAndCalculate(ref int largestArea, Stack<int> stack, int[] height, int rightIndex)
        {
            int length = height.Length; // 6

            int lastHeight = height[stack.Pop()]; // 2
            int width = stack.Count == 0 ? rightIndex : rightIndex - stack.Peek() - 1; // 1

            largestArea = Math.Max(largestArea, lastHeight * width); // 2 * 1
        }
}