Sign in

Given an array of strings words representing an English Dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.

Example 1:

I knew that the best solution is “Tire”. But, I used Hash first and that is method of brute force. I will used “Tire” later.
Sort first. check the word with hashset one by one. If those words are include in hashset, I will compare length of result and the word, and replace result to longer word.

我知道這題的最佳解是用Tire,先使用Hash的方式解這題,之後會再用Tire解一次,先來說明暴力解的方式。
暴力解:
先做排序,逐一檢查每個字的前面字串是否有存在hash裡面。如果沒有,就表示這個字串並不符合。如果有,則檢查是否為最長的字。


Given a string s and a string array dictionary, return the longest string in the dictionary that can be formed by deleting some of the given string characters. If there is more than one possible result, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Because return the longest word with the smallest lexicographical order. So, I need sort dictionary first. Each of two arrays have a pointer. Base on dictionary array and check s string one by one to find the same as char of dictionary. Record the string of dictionary, if satisfaction condition. I compare and get the longest word of dictionary, then return it.

因為同樣長度的字典要輸出字典排序最前面的字串,所以先針對字典的樹組做排序,兩個數組分別各自一個指針,以字典的數組為主,逐一檢查在s字串中是否都有字典中單一字串的字元。記錄滿足條件下的字典字串,同時比較滿足條件的字串長度,更新最長字串的字串作為最後輸出。


Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Right point start from 0 and shift to left. Left point start from length-1 and shift to right. Until find different character of right and left point. Check remain string is it a palindrome string, when right point shift to left 1 step or left point shift to right 1 step. I need check two conditions. If both true, return true. Otherwise, return false.

左指針從0開始往右,右指針從length-1開始往左,兩指針向中間前進,直到找到字元不相同的時候。將剩餘的子字串拿出來比對,看看是否在移除1個字元後剩餘的子字串就為相同,有可能是右指針往左,也有可能是左指針需要往右,所以兩個方式都需要判斷,兩者只要其一為true即為true。


Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

I suppose first this question is extension of Two Sum. Then I used HashSet to solve this question. But… The RunTime is too bad. So, I change my thinking to Two Points. small point is start from 0 and shift to right, large point is start from squrt(c) and shift to left. If sum of square of small point and square of large point lesser equal c, return true. If lesser than c, small point shift to right. If larger than c, large point shift to left.

一開始的思考方向是Two Sum的延伸,於是先做了一個HashSet的方式,但RunTime實在太差,練習使用TwoPoints。小指針從0開始往右移動,大指針從c開平方的整數值開始往左移動,如果小指針的平方與大指針的平方和為c,則為true。如果大於c則表示大指針過大,需要往左邊移動。反之,則小指針往右移動。


You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by…


Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.


Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.

We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).

Example…


You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). …


Given two arrays of integers nums and index. Your task is to create target array under the following rules:

  • Initially target array is empty.
  • From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
  • Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:


You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Return a list of integers representing the size of these parts.

Example 1:

Array fast than HashMap.
Recording the last position of every letter and saving in Array or HashMap.
Sweeping string of input again. setting the end point is the maximum. when the index position is equal to the end point, it means that an interval ends. calculate the difference with start point and end point.
先針對每個字母去紀錄最後一次出現的位置,將位置存在Array或是HashMap,
再掃一次字串,將結束點設為最大值,當索引位置等於結束點,則表示一個區間結束並將起始點設在結束點的後面一的地方。

SP Hou

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store