# [Java][Arrays][LeetCode] Longest Word in Dictionary #720

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:

`Input: words = ["w","wo","wor","worl","world"]Output: "world"Explanation: The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".`

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.

# [Java][TwoPoints][LeetCode] Longest Word in Dictionary through Deleting #524

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:

`Input: s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]Output: "apple"`

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.

# [Java][TwpPoints][LeetCode] Valid Palindrome II #680

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

Example 1:

`Input: s = "aba"Output: true`

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.

# [Java][TwoPoints][LeetCode] Sum of Square Numbers #633

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

Example 1:

`Input: c = 5Output: trueExplanation: 1 * 1 + 2 * 2 = 5`

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.

# [Java][TwoPoints][LeetCode] Merge Sorted Array #88

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 the function, but instead be stored inside the array `nums1`. To accommodate this, `nums1` has a length of `m + n`, where the first `m` elements denote the elements that should be merged, and the last `n` elements are set to `0` and should be ignored. `…`

# [Java][TwoPoint][LeetCode] Two Sum II — Input array is sorted #167

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`.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

`Input: numbers = [2,7,11,15], target = 9Output: [1,2]Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.`

It’s a two reverse…

# [Java][Greedy][LeetCode] Non-decreasing Array #665

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 1:

`Input: nums = [4,2,3]Output: trueExplanation: You could modify the first 4 to 1 to get a non-decreasing array.`

One by one to look for the point that happen decreasing. The counter will +1 when the event was happened. Because array can be modified one time. So, if…

# [Java][Greedy][LeetCode] Queue Reconstruction by Height #406

You are given an array of people, `people`, which are the attributes of some people in a queue (not necessarily in order). Each `people[i] = [hi, ki]` represents the `ith` person of height `hi` with exactly `ki` other people in front who have a height greater than or equal to `hi`.

Reconstruct and return the queue that is represented by the input array `people`. The returned queue should be formatted as an array `queue`, where `queue[j] = [hj, kj]` is the attributes of the `jth` person in the queue (`queue[0]` is the person at the front of the queue).

Example…

# [Java][Array][LeetCode] Create Target Array in the Given Order #1389

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:

`Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]Output: [0,4,1,3,2]`

# [Java][Greedy][LeetCode] PartitionLabels #763

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:

`Input: s = "ababcbacadefegdehijhklij"Output: [9,7,8]Explanation:The partition is "ababcbaca", "defegde", "hijhklij".This is a partition so that each letter appears in at most one part.A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits s into less parts.`

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.

## SP Hou

Get the Medium app