算法 第五章 單詞查找樹5.2

5.2 單詞查找樹

我們可以利用字符串的性質(zhì)進(jìn)行字符串的查找婆殿，以便用于字符串作為被查找的鍵的一般應(yīng)用程序语盈。

具體來說击胜，本節(jié)的算法在一般應(yīng)用場景中（甚至對于巨型的符號表）都能取得以下性能：

  • 查找命中所需的時(shí)間與被查找的鍵的長度成正比；
  • 查找未命中只需要檢查若干個(gè)字符割疾；
image-20200824140322606.png

這份API和第三章的符號表API有以下不同：

  • 將泛型的Key類型轉(zhuǎn)換為了具體的類型String馋艺。
  • 添加了三個(gè)方法:longestPrefixOf()栅干、keysWithPrefix()和keysThatMatch().

從字符串的排序算法可以看到迈套，指定字符串的字母表是十分重要的捐祠。對小型字母表的簡單而高效的實(shí)現(xiàn)不適用于大型字母表，這是因?yàn)楹笳呦牡目臻g太多桑李。

下面使用 she sells sea shells by the shore這幾個(gè)鍵作為示例描述以下三個(gè)方法踱蛀。

  • longestPrefixOf() 接受一個(gè)字符串參數(shù)并返回符號表中該字符串的前綴中最長的鍵，對于以上所有鍵贵白，longestPrefixOf("shell")的結(jié)果是she率拒，longestPrefixOf("shellsort")的結(jié)果是shells。
  • keysWithPrefix()接受一個(gè)字符串參數(shù)并返回符號表中所有以該字符串作為前綴的鍵禁荒，對于以上所有鍵猬膨，keysWithPrefix("she")結(jié)果是she和shells，keysWithPrefix("se")結(jié)果是sells和sea呛伴。
  • keysThatMatch()接受一個(gè)字符串參數(shù)并返回符號表中所有和該字符串匹配的鍵勃痴，其中參數(shù)點(diǎn)（‘.’）可以匹配任何字符谒所。對于以上所有鍵，keysThatMatch(".he")的結(jié)果是she和the沛申，keysThatMatch("s...")結(jié)果是she和sea劣领。

5.2.1 單詞查找樹

它由字符串鍵中的所有字符構(gòu)造而成，允許使用被查找鍵中的字符進(jìn)行查找铁材。

5.2.1.1 基本性質(zhì)

和各種查找樹一樣尖淘，單詞查找樹也是由鏈接的節(jié)點(diǎn)所組成的數(shù)據(jù)結(jié)構(gòu)，這些鏈接可能為空著觉。也可能指向其他結(jié)點(diǎn)村生，稱為它的父節(jié)點(diǎn)（只有一個(gè)節(jié)點(diǎn)除外，根節(jié)點(diǎn)饼丘，沒有任何節(jié)點(diǎn)指向根節(jié)點(diǎn)）梆造。每個(gè)節(jié)點(diǎn)含有R條鏈接，其中R為字母表的大小葬毫。單詞查找樹一般都含有大量的空鏈接镇辉，因此在繪制一顆單詞查找樹的時(shí)候一般會忽略空鏈接。盡管鏈接指向的是節(jié)點(diǎn)贴捡，但是也可以看成鏈接指向的是另一顆單詞查找樹忽肛，它的根節(jié)點(diǎn)就是被指向的節(jié)點(diǎn)。每個(gè)鏈接都對應(yīng)著一個(gè)字符--因?yàn)槊織l鏈接都只能指向一個(gè)節(jié)點(diǎn)烂斋，所以可以用鏈接所對應(yīng)的字符標(biāo)記被指向的節(jié)點(diǎn)（根節(jié)點(diǎn)除外屹逛，因?yàn)闆]有鏈接指向它）。每個(gè)節(jié)點(diǎn)也含有一個(gè)對應(yīng)的值汛骂，可以是空也可以是符號表中的某個(gè)鍵所關(guān)聯(lián)的值罕模。具體來說，我們將每個(gè)鍵所關(guān)聯(lián)的值保存在該鍵的最后一個(gè)字母所對應(yīng)的節(jié)點(diǎn)中帘瞭。

image-20200824143102875.png

5.2.1.2 單詞查找樹中的查找操作

在單詞查找樹中查找給定字符串是一個(gè)很簡單的過程淑掌，它是以被查找的鍵中的字符為導(dǎo)向的。單詞查找樹中的每個(gè)節(jié)點(diǎn)都包含了下一個(gè)可能出現(xiàn)的所有字符的鏈接蝶念。從根節(jié)點(diǎn)開始抛腕，首先經(jīng)過的是鍵的首字母所對應(yīng)的鏈接；在下一個(gè)節(jié)點(diǎn)中沿著第二個(gè)字符所對應(yīng)的鏈接繼續(xù)前進(jìn)媒殉；在第二個(gè)節(jié)點(diǎn)中沿著第三個(gè)字符所對應(yīng)的鏈接向前担敌，如此這般直到最后一個(gè)字母所指向的節(jié)點(diǎn)或者遇到了一條空鏈接。這時(shí)可能出現(xiàn)下面三種情況廷蓉。

  • 鍵的尾字符所對應(yīng)的結(jié)點(diǎn)值非空（如圖查找shells和she的示例）全封。這是一次命中的查找-鍵所對應(yīng)的值就是鍵的衛(wèi)子夫所對應(yīng)的結(jié)點(diǎn)保存的值。
  • 鍵的尾字符所對應(yīng)的結(jié)點(diǎn)中的值為空。（如查找shell）這是一次未命中的查找-符號表中不存在被查找的鍵
  • 查找結(jié)束于一條空鏈接（如查找shore）刹悴。這也是未命中的查找
image-20200824143657535.png

5.2.1.3 單詞查找樹中的插入操作

在插入之前要進(jìn)行一次查找：在單詞查找樹中意味著沿著被查找的鍵的所有字符到達(dá)樹中表示尾字符的結(jié)點(diǎn)或一個(gè)空鏈接给猾。此時(shí)會遇到以下兩種情況。

  • 在到達(dá)鍵尾字符之前就遇到了一個(gè)空鏈接颂跨。在這種情況下敢伸，單詞查找樹中不存在與鍵的尾字符對應(yīng)的結(jié)點(diǎn)，因此需要為鍵中還未被檢查的每個(gè)字符創(chuàng)建一個(gè)對應(yīng)的結(jié)點(diǎn)并且將鍵的值保存到最后一個(gè)字符的結(jié)點(diǎn)中
  • 在遇到空鏈接之前就遇到了尾字符恒削。在這種情況下池颈，和關(guān)聯(lián)數(shù)組一樣，將該結(jié)點(diǎn)的值設(shè)為鍵所對應(yīng)的值（無論該值是否非空）
image-20200824144117253.png

5.2.1.4 結(jié)點(diǎn)的表示

在開頭提過钓丰，我們?yōu)閱卧~查找樹所繪出的圖像和在程序中構(gòu)造的數(shù)據(jù)結(jié)構(gòu)并不完全一致躯砰，因?yàn)槲覀儧]有畫出空鏈接，將空鏈接考慮進(jìn)來將會突出單詞查找樹的以下重要性質(zhì)：

  • 每個(gè)結(jié)點(diǎn)都含有R個(gè)鏈接携丁，對應(yīng)著每個(gè)可能出現(xiàn)的字符
  • 字符和鍵均隱式地保存在數(shù)據(jù)結(jié)構(gòu)中

例如下面:所有的鍵都由小寫字母組成琢歇，每個(gè)結(jié)點(diǎn)都含有一個(gè)值和26個(gè)鏈接。第一條鏈接指向的子單詞查找樹中的所有鍵的首字母都是a梦鉴，第二條鏈接指向的子單詞查找樹中的所有鍵的首字母都是b李茫。

image-20200824144431964.png

在單詞查找樹中，鍵是由根節(jié)點(diǎn)到含有非空值的結(jié)點(diǎn)的路徑所隱式表示的肥橙。例如魄宏，sea關(guān)聯(lián)的值是2，因?yàn)楦?jié)點(diǎn)的第19條鏈接（指向所有以s開頭的鍵組成的子單詞查找樹）非空存筏，下一個(gè)結(jié)點(diǎn)中的第5條鏈接（指向所有以se開頭的鍵組成的子單詞數(shù)）非空宠互，第三個(gè)結(jié)點(diǎn)中的第1條鏈接（指向所有以sea開頭的鍵組成的子單詞查找樹）的值為2。數(shù)據(jù)結(jié)構(gòu)既沒有保存字符串sea也沒有保存字符s椭坚、e和a予跌。事實(shí)上，數(shù)據(jù)結(jié)構(gòu)沒有存儲任何字符串或字符善茎，保存了鏈接數(shù)組和值券册。因?yàn)閰?shù)R的作用的重要性,所以將基于含有R個(gè)字符的字母表的單詞查找樹稱為R向單詞查找樹。

有了這些預(yù)備知識后巾表，實(shí)現(xiàn)單詞查找樹就比較簡單了

/**
 * 基于單詞查找樹的符號表
 */
public class TrieST<Value> {
    private static final int R = 256; //基數(shù)
    private Node root;              //單詞查找樹的根節(jié)點(diǎn)

    private static class Node {
        private Object val;
        private Node[] next = new Node[R];
    }

    public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null) return null;
        else return (Value) x.val;
    }

    public Node get(Node x, String key, int d) {
        //返回以x作為根節(jié)點(diǎn)的子單詞查找樹中與key相關(guān)聯(lián)的值
        if (x == null) return null;
        if (d == key.length()) return x;
        char c = key.charAt(d);
        return get(x.next[c], key, d + 1);
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }

    private Node put(Node x, String key, Value val, int d) {
        //如果key存在于以x為根節(jié)點(diǎn)的子單詞查找樹中則更新與它相關(guān)聯(lián)的值
        if (x == null) x = new Node();
        if (d == key.length()) {
            x.val = val;
            return x;
        }
        char c = key.charAt(d);
        x.next[c] = put(x.next[c], key, val, d + 1);
        return x;
    }
}

5.2.1.5 大小

size()方法實(shí)現(xiàn)有以下三種顯而易見的選擇汁掠。

  • 即時(shí)實(shí)現(xiàn)：用一個(gè)實(shí)例變量N保存鍵的數(shù)量
  • 更加即時(shí)的實(shí)現(xiàn)：用結(jié)點(diǎn)的實(shí)例變量保存子單詞查找樹中鍵的數(shù)量略吨，在遞歸的put()和delete()方法調(diào)用之后更新它們集币。
  • 延時(shí)遞歸實(shí)現(xiàn)：遍歷單詞查找樹，返回結(jié)果
/**
     * 單詞查找樹的延時(shí)遞歸方法
     *
     * @return 返回一共有多少個(gè)鍵
     */
    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null) return 0;
        int cnt = 0;
        if (x.val != null) cnt++;
        for (char c = 0; c < R; c++) {
            cnt += size(x.next[c]);
        }
        return cnt;
    }

5.2.1.6 查找所有鍵

因?yàn)樽址玩I是隱式地表示在單詞查找樹中翠忠。在單詞查找樹中鞠苟，不僅要能夠在數(shù)據(jù)結(jié)構(gòu)中找到這些鍵，還需要顯示的表示它們。我們用一個(gè)類似于size()的私有遞歸方法collect()來完成這個(gè)任務(wù)当娱，它維護(hù)了一個(gè)字符串來保存從出發(fā)路徑上的一系列字符吃既。每當(dāng)我們在collect()調(diào)用訪問一個(gè)結(jié)點(diǎn)的時(shí)候，方法的第一個(gè)參數(shù)就是該結(jié)點(diǎn)跨细，第二個(gè)參數(shù)就是和該結(jié)點(diǎn)相關(guān)聯(lián)的字符串（從根節(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的所有字符）鹦倚。在訪問一個(gè)結(jié)點(diǎn)時(shí)，如果值為空冀惭，就將它和關(guān)聯(lián)的字符串加入隊(duì)列中震叙，然后遞歸的訪問它的鏈接數(shù)組所指向的所有可能的字符結(jié)點(diǎn)。每次調(diào)用之前散休，都將鏈接所對應(yīng)的字符附加到當(dāng)前鍵的末尾作為符號表中所有的鍵媒楼。用collect()方法為API中的keys()和keysWithPrefix()方法收集符號表中所有的鍵。要實(shí)現(xiàn)keys方法戚丸，可以以空字符串作為參數(shù)調(diào)用keysWithPrefix()方法划址。要實(shí)現(xiàn)KeysWithPrefix()方法，可以先調(diào)用get()找出給定前綴所對應(yīng)的單詞查找樹（如果不存在則返回null）限府，再使用collect()方法完成任務(wù)夺颤。

image-20200824150326540.png
image-20200824150333587.png
 /**
     * 返回所有的鍵
     *
     * @return 返回單詞查找樹中的所有的鍵
     */
    public Iterable<String> keys() {
        return keysWithPrefix("");
    }

    public Iterable<String> keysWithPrefix(String pre) {
        Deque<String> q = new ArrayDeque<>();
        collect(get(root, pre, 0), pre, q);
        return q;
    }

    private void collect(Node x, String pre, Queue<String> queue) {
        if (x == null) return;
        if (x.val != null) queue.add(pre);
        for (char r = 0; r < R; r++) {
            collect(x.next[r], pre + r, queue);
        }
    }

5.2.1.7 通配符匹配

我們可以用一個(gè)類似的過程實(shí)現(xiàn)keysThatMatch(),但需要collect()添加一個(gè)參數(shù)來指定匹配的模式。如果模式中含有通配符胁勺，就需要遞歸調(diào)用處理所有的鏈接拂共，否則只需要考慮處理指定的字符即可。

/**
     * 通配符匹配
     *
     * @param pat 通配符
     * @return 和通配符匹配的鍵
     */
    public Iterable<String> keyThatMatch(String pat) {
        Queue<String> q = new ArrayDeque<>();
        collect(root, "", pat, q);
        return q;
    }

    private void collect(Node x, String pre, String pat, Queue<String> queue) {
        int d = pre.length();
        if (x == null) return;
        if (d == pat.length() && x.val != null) {
            queue.add(pre);
            return;
        }
        if (d == pat.length()) return;
        char next = pat.charAt(d);
        for (char r = 0; r < R; r++) {
            if (next == '.' || r == next) {
                collect(x.next[r], pre + r, pat, queue);
            }
        }
    }

5.2.1.8 最長前綴

為了找到給定字符串的最長前綴姻几，需要一個(gè)類似于get()的遞歸方法宜狐。它會記錄查找路徑上所找到的最長鍵的長度。查找會在被查找的字符串結(jié)束或者遇到空鏈接終止

 public String longestPrefixOf(String s) {
        int length = search(root, s, 0, 0);
        return s.substring(0, length);
    }

    private int search(Node x, String s, int d, int length) {
        if (x == null) return length;
        if (x.val != null) length = d;
        if (d == s.length()) return length;
        char c = s.charAt(d);
        return search(x.next[c], s, d + 1, length);
    }

5.2.1.9 刪除操作

從單詞查找樹刪除一個(gè)鍵值對的第一步是蛇捌，找到所對應(yīng)的結(jié)點(diǎn)并將它的值設(shè)為null抚恒。如果該結(jié)點(diǎn)含有一個(gè)非空結(jié)點(diǎn)，則不需要任何其他操作络拌。如果它的所有鏈接均為空俭驮，則刪除這個(gè)結(jié)點(diǎn)，如果刪除它使得它的父節(jié)點(diǎn)也為空春贸，則刪除它的父節(jié)點(diǎn)混萝，以此類推。

public void delete(String key) {
        delete(root, key, 0);
    }

    private Node delete(Node x, String key, int d) {
        if(x==null) return null;
        if(d==key.length())
            x.val=null;
        else {
            char c=key.charAt(d);
            x.next[c]=delete(x,key,d+1);
        }
        if(x.val!=null) return x;
        for(char c=0;c<R;c++){
            if(x.next[c]!=null) return x;
        }
        return null;
    }
image-20200824151450388.png

5.2.2 單詞查找樹的性質(zhì)

image-20200824151531564.png

5.2.2.1 最壞情況下查找和插入操作的時(shí)間界限

image-20200824151615459.png

5.2.2.2 查找未命中的預(yù)期時(shí)間界限

image-20200824151649481.png

5.2.2.3 空間

image-20200824151708225.png

5.2.3 三向單詞查找樹

為了避免R向單詞查找樹過度的空間消耗萍恕，我們學(xué)習(xí)另一種數(shù)據(jù)的表示方法：三向單詞查找樹（TST）逸嘀。在三向單詞查找樹中，每個(gè)結(jié)點(diǎn)都含有一個(gè)字符允粤、三條鏈接和一個(gè)值崭倘。這三條鏈接分別對應(yīng)著當(dāng)前字母小于翼岁、等于和大于結(jié)點(diǎn)字母的所有鍵。在R向單詞查找樹中司光，樹的節(jié)點(diǎn)含有R條鏈接琅坡，每個(gè)非空鏈接的索引隱式的表示了他所對應(yīng)的字符。在等價(jià)的三向單詞查找樹中残家，字符是顯示地保存在節(jié)點(diǎn)中--只有沿著中間鏈接前進(jìn)的時(shí)候才會根據(jù)字符找到表中的鍵榆俺。

查找與插入操作

用三向單詞查找樹實(shí)現(xiàn)符號表API中的查找和插入操作很簡單。在查找的時(shí)候坞淮，我們首先比較首字母和根節(jié)點(diǎn)的字母谴仙。如果鍵的首字母較小，就選擇左鏈接碾盐；如果較大晃跺，就選擇右鏈接；如果相等毫玖，就選擇中鏈接掀虎。然后,遞歸地使用相同的算法。如果遇到了空鏈接或者當(dāng)前結(jié)束時(shí)點(diǎn)的值為空付枫，那么查找未命中烹玉。如果結(jié)束時(shí)鍵非空，那么查找命中

image-20200824153233700.png
image-20200824153242328.png

基于三向單詞查找樹的符號表

/**
 * 三向單詞查找樹
 */
public class TST<Value> {
    private Node root;  //樹的根節(jié)點(diǎn)

    private class Node {
        char c;                 //字符
        Node left, mid, right;    //左中右子三向單詞查找樹
        Value val;              //和字符串相關(guān)聯(lián)的值
    }

    public void put(String key, Value val) {
        root = put(root, key, val, 0);
    }

    public Node put(Node x, String key, Value val, int d) {
        char c = key.charAt(d);
        if (x == null) {
            x = new Node();
            x.c = c;
        }
        if (x.c > c)
            x.left = put(x.left, key, val, d + 1);
        if (x.c < c)
            x.right = put(x.right, key, val, d + 1);
        else if (d < key.length() - 1) {
            x.mid = put(x.mid, key, val, d + 1);
        } else x.val = val;
        return x;
    }

    public Value get(String key) {
        Node x = get(root, key, 0);
        if (x == null) return null;
        return x.val;
    }

    private Node get(Node x, String key, int d) {
        if (x == null) return null;
        char c = key.charAt(d);
        if (x.c > c) return get(x.left, key, d + 1);
        else if (x.c < c) return get(x.right, key, d + 1);
        else if (d < key.length() - 1) return get(x.mid, key, d + 1);
        else return x;
    }
}

5.2.4 三向單詞查找樹的性質(zhì)

5.2.4.1 空間

image-20200824153409848.png

5.2.4.2 查找成本

image-20200824153434936.png

5.2.5 應(yīng)使用字符串符號表的哪種實(shí)現(xiàn)

image-20200824153512708.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末阐滩，一起剝皮案震驚了整個(gè)濱河市二打，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌掂榔，老刑警劉巖继效，帶你破解...
    沈念sama閱讀 211,194評論 6贊 490
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異装获，居然都是意外死亡瑞信，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,058評論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門穴豫，熙熙樓的掌柜王于貴愁眉苦臉地迎上來凡简，“玉大人，你說我怎么就攤上這事精肃〕由” “怎么了？”我有些...
    開封第一講書人閱讀 156,780評論 0贊 346
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵司抱，是天一觀的道長筐眷。 經(jīng)常有香客問我，道長状植，這世上最難降的妖魔是什么浊竟？ 我笑而不...
    開封第一講書人閱讀 56,388評論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任怨喘，我火速辦了婚禮津畸，結(jié)果婚禮上振定，老公的妹妹穿的比我還像新娘。我一直安慰自己肉拓，他們只是感情好后频，可當(dāng)我...
    茶點(diǎn)故事閱讀 65,430評論 5贊 384
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著暖途，像睡著了一般卑惜。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上驻售，一...
    開封第一講書人閱讀 49,764評論 1贊 290
  • 城市分裂傳說
    那天露久，我揣著相機(jī)與錄音，去河邊找鬼欺栗。 笑死毫痕，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的迟几。 我是一名探鬼主播消请，決...
    沈念sama閱讀 38,907評論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼类腮！你這毒婦竟也來了臊泰？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 37,679評論 0贊 266
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對情侶失蹤蚜枢，失蹤者是張志新（化名）和其女友劉穎缸逃，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體厂抽，經(jīng)...
    沈念sama閱讀 44,122評論 1贊 303
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡察滑，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,459評論 2贊 325
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了修肠。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片贺辰。...
    茶點(diǎn)故事閱讀 38,605評論 1贊 340
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖嵌施，靈堂內(nèi)的尸體忽然破棺而出饲化，到底是詐尸還是另有隱情，我是刑警寧澤吗伤，帶...
    沈念sama閱讀 34,270評論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布吃靠，位于F島的核電站，受9級特大地震影響足淆，放射性物質(zhì)發(fā)生泄漏巢块。R本人自食惡果不足惜礁阁，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,867評論 3贊 312
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望族奢。 院中可真熱鬧姥闭，春花似錦、人聲如沸越走。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,734評論 0贊 21
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽廊敌。三九已至铜跑，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間骡澈，已是汗流浹背锅纺。 一陣腳步聲響...
    開封第一講書人閱讀 31,961評論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留肋殴，地道東北人囤锉。 一個(gè)月前我還...
    沈念sama閱讀 46,297評論 2贊 360
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像疼电，于是被迫代替她去往敵國和親嚼锄。 傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,472評論 2贊 348