Java 解法, 执行用时: 32ms, 内存消耗: 10348K, 提交时间: 2023-02-22 09:41:14

import java.util.HashSet;
import java.util.Scanner;

/**
 * @author 11214
 * @since 2023/2/22 9:35
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = 1;
        boolean flag = false;
        HashSet<String> set = new HashSet<>(128);
        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            if (s.equals("9")) {
                set.clear();
                if (!flag) {
                    System.out.println("Set " + t + " is immediately decodable");
                }
                flag = false;
                t += 1;
            }
            if (flag) {
                continue;
            }

            for (int i = 1; i <= s.length(); i++) {
                String substring = s.substring(0, i);
                if (set.contains(substring)) {
                    System.out.println("Set " + t + " is not immediately decodable");
                    flag = true;
                }
            }
            set.add(s);
        }
    }
}

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 376K, 提交时间: 2019-12-09 18:20:07

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

const int MAXN = 800;

struct Node {
  bool val;
  int ch[10];
};
Node nodes[MAXN];
int sz;

bool insert(string s) {
  bool isDup = false;
  int bsz = sz;
  int cur = 0;
  for (auto ch: s) {
    int id = ch - '0';
    int &nxt = nodes[cur].ch[id];
    if (nxt == 0) nxt = ++sz;
    cur = nxt;
    if (nodes[cur].val) isDup = true;
  }
  nodes[cur].val = true;
  if (bsz == sz) isDup = true;
  return isDup;
}

int main() {
  string s;
  int Te = 0;
  bool isDup = false;
  while (cin >> s) {
    if (s == "9") {
      memset(nodes, 0, sizeof(nodes));
      sz = 0;
      cout << "Set " << ++Te << " is " << (isDup?"not ":"") << "immediately decodable" << endl;
      isDup = false;
      continue;
    }
    if (insert(s)) isDup = true;
  }

}

C++ 解法, 执行用时: 2ms, 内存消耗: 424K, 提交时间: 2021-12-05 15:16:34

#include<bits/stdc++.h>
using namespace std;
int trie[5000][2],tot;
bool f[5000];
char s[11];
bool insert(char s[]){
	int r = 0,*p;
	bool flag = 1;
	for (int i = 0;s[i];i++){
		p = &trie[r][s[i] - '0'];
		if (f[*p])return 1;
		if (!*p){
			*p = ++tot;
			flag = 0;
		}
		r = *p;
	}
	f[r] = 1;
	return flag;
}
int main(){
	bool flag;
	for (int i = 1;cin>>s;i++){
		memset(trie,0,sizeof(trie));
		memset(f,0,sizeof(f));
		tot = 0;
		flag = 0;
		do{
			if (s[0] == '9')break;
			if (!flag)
				if (insert(s))
					flag = 1;
		}while (cin>>s);
		printf("Set %d is ",i);
		if (flag)printf("not ");
		printf("immediately decodable\n");
	}
	return 0;
}