Press "Enter" to skip to content

Posts tagged as “string”

花花酱 LeetCode 680. Valid Palindrome II

Problem:

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:

Example 2:

Note:

  1. The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

Idea:

Greedy, delete the first unmatched char



Time complexity

O(n)

Solution:

 

花花酱 LeetCode 241. Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +- and *.

Example 1:

Input: "2-1-1".

Output: [0, 2]

Example 2:

Input: "2*3-4*5"

Output: [-34, -14, -10, -10, 10]

Solution:

Running time: 3ms

C++

Python3

花花酱 Leetcode 139. Word Break

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

UPDATE (2017/1/4):
The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

 

Idea:

DP

Time complexity O(n^2)

Space complexity O(n^2)

Solutions:

C++

C++ V2 without using dict. Updated: 1/9/2018

 

Java

Python

 

花花酱 LeetCode 451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Example 2:

Example 3:

Solution:

 

花花酱 LeetCode 520. Detect Capital

Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

  1. All letters in this word are capitals, like “USA”.
  2. All letters in this word are not capitals, like “leetcode”.
  3. Only the first letter in this word is capital if it has more than one letter, like “Google”.

Otherwise, we define that this word doesn’t use capitals in a right way.

Example 1:

Example 2:

Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.