Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.5 kB
1
Indexable
Never
package Magic_String;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class UserSolution {
	class MyWord {
		int deathTime;
		boolean isLiving;
		int[] count = new int[11];
		MyWord parent;

		public MyWord() {
			this.isLiving = true;

			this.parent = this;
		}

	}

	// Disjoint Set
	private MyWord find(MyWord word) {
		if (word.parent == word) {
			return word;
		}
		return find(word.parent);
	}

	private void union(MyWord w1, MyWord w2) {
		MyWord w1_parent = find(w1);
		MyWord w2_parent = find(w2);
		if (w1_parent == w2_parent) {
			return;
		}
		w2.parent = w1;
		for (int i = 5; i < 11; i++) {
			w1.count[i] += w2.count[i];
		}
		w2.isLiving = false;
	}

	private void update(MyWord w, int Timestamp) {
		if (w.deathTime <= Timestamp) {
			w.isLiving = false;
		}
	}

	//HashMap<String, MyWord> wordMap = new HashMap<>();
	List<MyWord> wordList = new ArrayList<>();
	MyWord[][][] wordMap=new MyWord[26][26][26];
	void init(int N) {
		wordList.clear();
		for(int i=0;i<26;i++){
			for(int j=0;j<26;j++){
				for(int k=0;k<26;k++){
					wordMap[i][j][k]=null;
				}
			}
		}
	}

	int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) {
		MyWord word = new MyWord();
		word.count[mLen]++;
		word.deathTime = mTimestamp + mLifespan;
		wordList.add(word);
		for (int i = 0; i < mLen - 2; i++) {
			int a=mStr[i]-'a';
			int b=mStr[i+1]-'a';
			int c=mStr[i+2]-'a';
			if(wordMap[a][b][c]!=null){
				MyWord tmp = wordMap[a][b][c];
				MyWord tmp_parent = find(tmp);
				update(tmp_parent, mTimestamp);
				if (tmp_parent.isLiving) {
					union(word, tmp_parent);
				}
			}
//			String s = "";
//			s = "" + mStr[i] + mStr[i + 1] + mStr[i + 2];
//			if (wordMap.containsKey(s)) {
//				MyWord tmp = wordMap.get(s);
//				MyWord tmp_parent = find(tmp);
//				update(tmp_parent, mTimestamp);
//				if (tmp_parent.isLiving) {
//					union(word, tmp_parent);
//				}
//			}
			wordMap[a][b][c]=word;
		}
		return checkString(mTimestamp, mLen);
	}

	int checkString(int mTimestamp, int mLen) {
		int ans = 0;
		List<MyWord> Del=new ArrayList<UserSolution.MyWord>();
		for (MyWord word : wordList) {
			update(word, mTimestamp);
			if (!word.isLiving) {
				Del.add(word);
			}
		}
		for(MyWord word:Del){
			wordList.remove(word);
		}
		for(MyWord word:wordList){
			ans+=word.count[mLen];
		}
		return ans;
	}

}