编程知识 cdmana.com

691. Sticker spelling: DFS + memorized search questions

Title Description

This is a LeetCode Upper 691. Sticker spelling , The difficulty is difficult .

Tag : 「 Memory search 」、「DFS」、「 State compression 」、「 Explosive search 」

We have n n Different stickers . Each sticker has a small English word .

You want to spell the given string target , The method is to cut individual letters from the collected stickers and rearrange them . If you will , You can use each sticker multiple times , The number of each sticker is unlimited .

Back you need to spell target  Minimum number of stickers . If the task is not possible , Then return to 1 -1 .

Be careful : In all test cases , All the words are from 1000 1000 A random selection of the most common American English words , also target  Selected as a connection between two random words .

Example 1:

 Input : stickers = ["with","example","science"], target = "thehat"

 Output :3

 explain :
 We can use  2  individual  "with"  stickers , and  1  individual  "example"  stickers .
 Cut and rearrange the letters on the sticker , You can form goals  “thehat“  了 .
 Besides , This is the minimum number of stickers required to form the target string .
 Copy code 

Example 2:

 Input :stickers = ["notice","possible"], target = "basicbasic"

 Output :-1

 explain : We can't form goals by cutting the letters of a given sticker “basicbasic”.
 Copy code 

Tips :

  • n = = s t i c k e r s . l e n g t h n == stickers.length
  • 1 < = n < = 50 1 <= n <= 50
  • 1 < = s t i c k e r s [ i ] . l e n g t h < = 10 1 <= stickers[i].length <= 10
  • 1 < = t a r g e t < = 15 1 <= target <= 15
  • stickers[i]  and  target  Made up of lowercase English words

DFS + Memory search

For convenience , We remember s s = s t i c k e r s ss = stickers , t = t a r g e t t = target , among t t The length of is n n .

We use one s t a t e state ( One int Type variable ) To represent the current t t The combination of : if t [ i ] t[i] Has been put together , It's in s t a t e state low i i Position as 1 1 , Otherwise 0 0 .

At the beginning state = 0, Finally, if we can make it t t , Then there are state = (1 << n) - 1.

Because each s s [ i ] ss[i] Can be used many times , So for a particular s t a t e state for , It is converted into the final (1 << n) - 1 The minimum number of steps is fixed , So we can use 「 Memory search 」 To avoid the same s t a t e state Repeat the search .

And in the one-step search process , We enumerate each s s [ i ] ss[i] To update s t a t e state , Suppose you use a s s [ i ] ss[i] The new status obtained is n s t a t e nstate , Then all of them dfs(nstate) + 1 The value of is the smallest f [ s t a t e ] f[state] .

Code :

class Solution {
    int N = 20, M = 1 << 20, INF = 50;
    int[] f = new int[M];
    String[] ss;
    String t;
    int dfs(int state) {
        int n = t.length();
        if (state == ((1 << n) - 1)) return 0;
        if (f[state] != -1) return f[state];
        int ans = INF;
        for (String s : ss) {
            int nstate = state;
            out:for (char c : s.toCharArray()) {
                for (int i = 0; i < n; i++) {
                    if (t.charAt(i) == c && ((nstate >> i) & 1) == 0) {
                        nstate |= (1 << i);
                        continue out;
                    }
                }
            }
            if (nstate != state) ans = Math.min(ans, dfs(nstate) + 1);
        }
        return f[state] = ans;
    }
    public int minStickers(String[] stickers, String target) {
        ss = stickers; t = target;
        Arrays.fill(f, -1);
        int ans = dfs(0);
        return ans == INF ? -1 : ans;
    }
}
 Copy code 
  • Time complexity : Make n n and m m Each represents a string t The length and array of ss The length of . share 2 n 2^n Status , The computational complexity of a single state is O ( i = 0 m 1 s s [ i ] . l e n g t h × n ) O(\sum_{i = 0}^{m - 1}ss[i].length \times n) . The overall complexity is O ( 2 n × i = 0 m 1 s s [ i ] . l e n g t h × n ) O(2^n \times \sum_{i = 0}^{m - 1}ss[i].length \times n)
  • Spatial complexity : O ( 2 n ) O(2^n)

Last

This is us. 「 Brush through LeetCode」 The first of the series No.691 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse :github.com/SharingSour… .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

版权声明
本文为[Gong Shui Sanye's Diary]所创,转载请带上原文链接,感谢
https://cdmana.com/2022/134/202205141227435056.html

Scroll to Top