算法leetcode

【搜索难题】力扣411-最短特异单词缩写

字数统计: 1.3k字   |   阅读时长: 6分
,

$1 题目

题目链接

411. 最短特异单词缩写

题目描述

字符串 “word” 包含以下这些缩写形式：

[“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]
给一个目标字符串和一个字符串字典，为目标字符串找一个 最短 长度的缩写字符串，同时这个缩写字符串不是字典中其他字符串的缩写形式。

缩写形式中每一个 数字 或者字母都被视为长度为 1 。比方说，缩写形式 “a32bc” 的长度为 4 而不是 5 。

注意:

1
2
如果像第二个示例一样有多个有效答案，你可以返回它们中的任意一个。
假设目标字符串的长度为 m ，字典中的字符串数目为 n 。你可以假设 m ≤ 21， n ≤ 1000， 且 log2(n) + m ≤ 20.

样例

示例:

“apple”, [“blade”] -> “a4” (因为 “5” 或者 “4e” 同时也是 “blade” 的缩写形式，所以它们是无效的缩写)

“apple”, [“plain”, “amber”, “blade”] -> “1p3” (其他有效的缩写形式还包括 “ap3”, “a3e”, “2p2”, “3le”, “3l1”)。

$2 题解

算法：搜索

1
2
3
枚举(搜索)所有 target 的缩写:
    每搜到一个缩写 t，当 `len(t) < min_len` 时:
        判定 t 是否是 words 中某个次的缩写，若都不是，更新答案。

组件1：枚举(搜索)所有 target 的缩写

基础搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        vector<string> result;
        dfs(word, 0, "", result);
        return result;
    }

private:
    void dfs(const string& word, int left, string item, vector<string>& result)
    {
        int n = word.size();
        if(left >= n)
        {
            result.push_back(item);
            return;
        }
        for(int i = left; i < n; ++i)
        {
            // [left, i) 是数字，i 是分格字符 [i + 1, n) 是下一个
            int len = i - left;
            string num = "";
            if(len > 0) num = to_string(len);
            dfs(word, i + 1, item + num + word[i], result);
        }
        dfs(word, n + 1, item + to_string(n - left), result);
    }
};
状态压缩维护子集型枚举

使用 0 代表没有被缩写的字符， 1 代表缩写的字符。

那么每一个缩写都一一对应到一个 n 位的二进制数字。搜索所有的缩写就相当于一个子集型的枚举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<string> generateAbbreviations(string word) {
        int n = word.size();
        vector<string> result((1 << n), "");
        for(int state = 0; state < (1 << n); ++state)
            result[state] = construct(state, word);
        return result;
    }

private:
    string construct(int state, const string& s)
    {
        int n = s.size();
        int i = 0;
        string result;
        while(i < n)
        {
            if(state >> i & 1)
            {
                // s[i] 用了缩写
                int j = i;
                while(j < n && (state >> j & 1))
                    ++j;
                result += to_string(j - i);
                i = j;
            }
            else
            {
                // s[i] 没用缩写
                result += s[i++];
            }
        }
        return result;
    }
};

组件2：判定 t 是否是 s 的缩写

算法：双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int n = word.size();
        int m = abbr.size();
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            // word[i], abbr[j]
            if(abbr[j] >= '0' && abbr[j] <= '9')
            {
                int r = j + 1;
                while(r < n && abbr[r] >= '0' && abbr[r] <= '9')
                    ++r;
                string str_len = abbr.substr(j, r - j);
                if(str_len.front() == '0')
                    return false;
                stringstream ss;
                ss << str_len;
                int len;
                ss >> len;
                i += len;
                j = r;
            }
            else
            {
                if(abbr[j] != word[i])
                    return false;
                ++i;
                ++j;
            }
        }
        // i >= n 或 j >= m
        return i == n && j == m;
    }
};

算法1: 基础搜索+剪枝

不用子集型枚举，就用基础搜索 + check 的方式，这样搜索过程中方便做一些剪枝

最优性剪枝

任何一步如果出现当前的 len 已经大于等于 min_len 了，可以剪枝。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Solution {
public:
    string minAbbreviation(string target, vector<string>& dictionary) {
        vector<string> dict;
        for(const string &s: dictionary)
            if(s.size() == target.size())
                dict.push_back(s);
        int n = target.size();
        int min_len = n;
        string ans = target;
        dfs(dict, target, 0, "", ans, 0, min_len);
        return ans;
    }

private:
    void dfs(const vector<string>& dictionary, const string& word, int left, string abbr, string& ans, int len, int& min_len)
    {
        if(len >= min_len)
            return;
        int n = word.size();
        if(left >= n)
        {
            bool flag = true;
            for(const string &s: dictionary)
                if(check(abbr, s))
                {
                    flag = false;
                    break;
                }
            if(flag)
            {
                min_len = len;
                ans = abbr;
            }
            return;
        }
        for(int i = left; i < n; ++i)
        {
            // [left, i) 是数字，i 是分格字符 [i + 1, n) 是下一个
            string num = "";
            int add_len = 1;
            if(i - left > 0)
            {
                num = to_string(i - left);
                ++add_len;
            }
            dfs(dictionary, word, i + 1, abbr + num + word[i], ans, len + add_len, min_len);
        }
        dfs(dictionary, word, n + 1, abbr + to_string(n - left), ans, len + 1, min_len);
    }

    bool check(const string abbr, const string& word)
    {
        int n = word.size();
        int m = abbr.size();
        int i = 0, j = 0;
        while(i < n && j < m)
        {
            // word[i], abbr[j]
            if(abbr[j] >= '0' && abbr[j] <= '9')
            {
                int r = j + 1;
                while(r < n && abbr[r] >= '0' && abbr[r] <= '9')
                    ++r;
                string str_len = abbr.substr(j, r - j);
                if(str_len.front() == '0')
                    return false;
                stringstream ss;
                ss << str_len;
                int len;
                ss >> len;
                i += len;
                j = r;
            }
            else
            {
                if(abbr[j] != word[i])
                    return false;
                ++i;
                ++j;
            }
        }
        // i >= n 或 j >= m
        return i == n && j == m;
    }
};
Share