Press "Enter" to skip to content

Posts published in “String”

花花酱 LeetCode 636. Exclusive Time of Functions

题目大意:给你一些函数的起始/终止时间的日志,让你输出每个函数的总运行时间。假设单核单线程,支持递归函数。

Given the running logs of n functions that are executed in a nonpreemptive single threaded CPU, find the exclusive time of these functions.

Each function has a unique id, start from 0 to n-1. A function may be called recursively or by another function.

A log is a string has this format : function_id:start_or_end:timestamp. For example, "0:start:0" means function 0 starts from the very beginning of time 0. "0:end:0" means function 0 ends to the very end of time 0.

Exclusive time of a function is defined as the time spent within this function, the time spent by calling other functions should not be considered as this function’s exclusive time. You should return the exclusive time of each function sorted by their function id.

Example 1:

Note:

  1. Input logs will be sorted by timestamp, NOT log id.
  2. Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.
  3. Two functions won’t start or end at the same time.
  4. Functions could be called recursively, and will always end.
  5. 1 <= n <= 100

Solution: Simulate using stack

 

花花酱 LeetCode 771. Jewels and Stones

题目大意:给你宝石的类型,再给你一堆石头,返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

  • S and J will consist of letters and have length at most 50.
  • The characters in J are distinct.

 

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

C++ v2

Java

Python

花花酱 LeetCode 282. Expression Add Operators

题目大意:给你一个字符串,让你在数字之间加上+,-,*使得等式的值等于target。让你输出所有满足条件的表达式。

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +-, or * between the digits so they evaluate to the target value.

Examples:

Slides:

 

Solution 1: DFS

Time complexity: O(4^n)

Space complexity: O(n^2) -> O(n)

C++

C++ / SC O(n)

Java

花花酱 LeetCode 763. Partition Labels

题目大意:把字符串分割成尽量多的不重叠子串,输出子串的长度数组。要求相同字符只能出现在一个子串中。

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Solution 0: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

Python

 

Solution 1: Greedy

Time complexity: O(n)

Space complexity: O(26/128)

C++

Java

Python3

 

花花酱 LeetCode 758. Bold Words in String

题目大意:给你一个字符串和一些要加粗的单词,返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between <b> and </b> tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "a<b>abc</b>d". Note that returning "a<b>a<b>b</b>c</b>d" would use more tags, so it is incorrect.

Note:

  1. words has length in range [0, 50].
  2. words[i] has length in range [1, 10].
  3. S has length in range [0, 500].
  4. All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.