讨论/面试考题/Google 面试题: 给定字符串, 生成unique id/
Google 面试题: 给定字符串, 生成unique id

题目

  • 每次生成的id必须是唯一的
  • 给定一个base string, 字符都是unique, 生成的 id 必须来自base string中
  • 保证每次输出都是当前最短的
  • 给定一个整数N, 保证连续的字符串不得大于N
class IdGenerator(object):
    def __init__(self, base_str, n):
        self.base_str = base_str
        self.n = n

    def do_generate():
        pass

我只想到一个比较暴力的算法, id 从长度为 1 开始生成, len = 1 的id都生成完了之后, 就生成 len = 2的.
这样能保证每次生成最短. 保证连续字符长度不得超过n的话, 可以做一些判断...
还有没有更好的idea?

展开讨论
共 3 个讨论

k进制,zsbd

能不能用散列实现,小白提问

暴搜做了

#include<bits/stdc++.h>
using namespace std;

string str;
int n;

void dfs( string st, int cnt, int sum, int len )
{
    if( sum == n + 1 || cnt == str.length() + 1 || st.length() > len ) return;
    if( sum && st.length() == len ) cout << st << endl;
    dfs( st, cnt + 1, 0, len );
    st = st + str[ cnt ];
    dfs( st, cnt + 1, sum + 1, len );
}

int main()
{
    cin >> str;
    cin >> n;
    for( int i = 1; i <= str.length(); i ++ )
    {
        string s;
        dfs( s, 0, 0, i );
    }
    return 0;
}