c# - フラットデータから木の葉を見つける方法

Question

私はこれに似たツリーデータを持っています:

[0] => 
      id = 5,
      name = "TV",
      parent_id = 1,
      children => 
                  [0] => 
                        id = 6,
                        name = "PLASMA",
                        parent_id = 5,
                        children = null
                  [1] =>
                        id = 7,
                        name = "LCD",
                        parent_id = 5,
                        children =>
                                    [0] =>
                                          id = 8,
                                          name = "Gloss",
                                          parent_id = 7,
                                          children = null
                                    [1] =>
                                          id = 9,
                                          name = "Matte",
                                          parent_id = 7,
                                          children = null
[1] =>
      id = 4,
      name = "Printers",
      parent_id = 1,
      children =>
                 ....

そして、次のようなフラット文字列データがあります。

• テレビ
• TV_PLASMA_光沢
• TV_LCD

「_」はサブカテゴリの区切り文字です。

カテゴリ ID の配列を見つけるための最適なアルゴリズムは何ですか?

入力例:

1. テレビ
2. TV_PLASMA_光沢
3. TV_LCD

出力例:

1. 配列: 5
2. 配列: 5、6、8
3. 配列: 5、7

言語は問題ではありません。これはアルゴリズムにすぎませんが、この場合は C# を優先します。

ありがとうございました。

Answer 1

HashMap(Dictionary<string, int>この場合は問題ありません) を使用して、ツリーを繰り返し処理し、(name, id) ペアを HashMap に追加します。

どの入力に対しても、入力文字列とハッシュマップを渡します。

• 区切り文字で文字列を分割します。この場合は「_」( input.Split(new char[]{'_'}))
• 各文字列部分について、ハッシュマップでその ID を検索し、それを出力文字列または配列に追加します

*

public int[] GetIDsFromString(string input, Dictionary<string, int> lookup)
{
  string stringParts = input.Split(new char[]{'_'});
  int[] retval = new int[stringParts.Length];
  int retIndex = 0;
  foreach(var s in stringParts)
    if (lookup.contains(s))
      retval[retIndex++] = lookup[s];
    else
      throw new Exception(string.format("string contained invalid item {0}", s));
  return retval;
}

Answer 2

名前に関連する ID の (逆) ルックアップに辞書を使用する

Dictionary<string,int> ids = new Dictionary<string,int>();
ids.Add("TV", 5);
ids.Add("PLASMA", 6);
// And so on

ここで、ID を検索する前に入力文字列を分割します

string input = "TV_PLASMA_Gloss";
string[] categories = input.Split('_');
int[] result = new int[categories.Length];
for (int i = 0; i < categories.Length; i++) {
    int id;
    if (ids.TryGetValue(categories[i], out id)) {
        result[i] = id;
    } else {
        result[i] = -1; // Unknown category
    }
}

Answer 3

それが方法です、私は再帰を使用してそれを行います：

文字列配列と構造体/オブジェクト配列などを受け取る関数を定義します。文字列配列は、関数を呼び出す前に解析されます。

string = "TV_PLASMA_Gloss"
array[0] = "TV"
array[1] = "PLASMA"
array[2] = "Gloss"

配列の最初の文字列は、すべての「最上位」エントリに対してテストされます。一致するエントリがあった場合、関数は残りの配列と一致したエントリで再度呼び出されます。

配列に文字列が 1 つしか残っていない場合は、見つかったエントリの ID を返します。このようにして、再帰呼び出しを行い、必要な integer-id-array を構築します。

呼び出し階層は次のようになります。

-> function({"TV","PLASMA","Gloss"}, entry)
   -> function({"PLASMA","Gloss"}, matched_entry)
       -> function({"Gloss"}, matched_entry)
       <- id = 8
   <- id = 6,8
<- id = 5,6,8